這道題做的我想哭啊。。WA了將近十次了吧
一開始我用數組模擬的隊列，后來和老大代碼對拍，感覺改的是基本都一模一樣了，還是WA
實在沒有辦法了，改用queue了
?
題目里的x是列y是行，和代碼里的反過來的，要注意！
題目里面說在起點的時候無論朝哪個方向走都不算一次轉彎，所以我們將方向和轉彎次數都賦值為-1，這樣就不用特殊處理了
入隊條件，拓展后的轉彎次數小于或等于vis數組中記錄的最小轉彎次數即可入隊
輸出結果，不要一搜到終點便急著輸出，應為可能后面再一次搜到終點的時候轉彎次數小于k
因此可以遍歷完以后再輸出，或者輸出yes的時候加一個限制條件：轉彎次數小于等于k
兩種處理方法，第二種更快一點
?
這里先把數組WA掉的代碼貼上，留著以后再找錯。
1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6 7 struct Point 8 { 9 int x, y; 10 int di, times; 11 }qu[20000 + 10]; 12 13 const int MAX = 200; 14 char map[105][105]; 15 int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; 16 int row, col, vis[105][105]; 17 int sx, sy, ex, ey, k; 18 int head, tail; 19 20 bool islegal(int x, int y) 21 { 22 if(x>=0 && x<row && y>=0 && y<col && map[x][y]=='.') 23 return true; 24 return false; 25 } 26 27 void BFS(void) 28 { 29 head = 0, tail = 1; 30 vis[sx][sy] = 0; 31 qu[0].x = sx, qu[0].y = sy; 32 qu[0].di = -1, qu[0].times = -1; 33 while(head < tail) 34 { 35 //if(qu[head].x==ex && qu[head].y==ey) 36 //{printf("yes\n"); return;} 37 for(int i = 0; i < 4; ++i) 38 { 39 int temp; 40 int xx = qu[head].x + dir[i][0]; 41 int yy = qu[head].y + dir[i][1]; 42 if(!islegal(xx, yy)) continue; 43 if(i != qu[head].di) 44 temp = qu[head].times + 1; 45 else 46 temp = qu[head].times; 47 if(temp > k) continue; 48 if(temp <= vis[xx][yy]) 49 { 50 vis[xx][yy] = temp; 51 qu[tail].x = xx, qu[tail].y = yy; 52 qu[tail].di = i; 53 qu[tail++].times = temp; 54 } 55 } 56 ++head; 57 } 58 if(vis[ex][ey] <= k) 59 printf("yes\n"); 60 else 61 printf("no\n"); 62 } 63 64 int main(void) 65 { 66 #ifdef LOCAL 67 freopen("1728in.txt", "r", stdin); 68 #endif 69 70 int T; 71 scanf("%d", &T); 72 while(T--) 73 { 74 scanf("%d%d", &row, &col); 75 getchar(); 76 for(int i = 0; i < row; ++i) 77 { 78 for(int j = 0; j < col; ++j) 79 { 80 scanf("%c", &map[i][j]); 81 vis[i][j] = MAX; 82 } 83 getchar(); 84 } 85 scanf("%d%d%d%d%d", &k, &sy, &sx, &ey, &ex); 86 --sx, --sy, --ex, --ey; 87 BFS(); 88 } 89 return 0; 90 }
?
queue的AC代碼：
1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <queue> 6 using namespace std; 7 8 struct Point 9 { 10 int x, y; 11 int di, times; 12 }qu[20000 + 10]; 13 14 const int MAX = 200; 15 char map[105][105]; 16 int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; 17 int row, col, vis[105][105]; 18 int sx, sy, ex, ey, k; 19 20 bool islegal(int x, int y) 21 { 22 return(x>=0 && x<row && y>=0 && y<col && map[x][y]=='.'); 23 } 24 25 void BFS(void) 26 { 27 queue<Point> qu; 28 vis[sx][sy] = 0; 29 Point cur; 30 cur.x = sx, cur.y = sy; 31 cur.di = cur.times = -1; 32 qu.push(cur); 33 while(!qu.empty()) 34 { 35 cur = qu.front(); 36 qu.pop(); 37 if(cur.x==ex&&cur.y==ey&&cur.times<=k) 38 { 39 printf("yes\n"); 40 return; 41 } 42 for(int i = 0; i < 4; ++i) 43 { 44 Point next = cur; 45 next.x += dir[i][0]; 46 next.y += dir[i][1]; 47 if(!islegal(next.x, next.y)) continue; 48 if(i != cur.di) 49 { 50 next.di = i; 51 ++next.times; 52 } 53 if(next.times > k) continue; 54 if(next.times <= vis[next.x][next.y]) 55 { 56 vis[next.x][next.y] = next.times; 57 qu.push(next); 58 } 59 } 60 } 61 printf("no\n"); 62 } 63 64 int main(void) 65 { 66 #ifdef LOCAL 67 freopen("1728in.txt", "r", stdin); 68 #endif 69 70 int T; 71 scanf("%d", &T); 72 while(T--) 73 { 74 scanf("%d%d", &row, &col); 75 getchar(); 76 for(int i = 0; i < row; ++i) 77 { 78 for(int j = 0; j < col; ++j) 79 { 80 scanf("%c", &map[i][j]); 81 vis[i][j] = MAX; 82 } 83 getchar(); 84 } 85 scanf("%d%d%d%d%d", &k, &sy, &sx, &ey, &ex); 86 --sx, --sy, --ex, --ey; 87 BFS(); 88 } 89 return 0; 90 }
?
對比了一下別人的代碼，才知道自己寫的代碼有多么挫。。
http://972169909-qq-com.iteye.com/blog/1244218
這里講了兩種方法，因為題目只是問能不能在轉k個彎之內到達，而不是轉的最小的彎，所以DFS也是能做的。30MS多點
1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6 7 const int MAX = 200; 8 char map[105][105]; 9 int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; 10 int row, col, vis[105][105]; 11 int sx, sy, ex, ey, k; 12 bool flag; 13 14 bool islegal(int x, int y) 15 { 16 return(x>=0 && x<row && y>=0 && y<col && map[x][y]=='.'); 17 } 18 19 void DFS(int x, int y, int di) 20 { 21 if(x==ex && y==ey && vis[ex][ey]<=k) 22 {flag = true; return;} 23 if(vis[x][y] > k) 24 return; 25 if(x!=ex && y!=ey && vis[x][y]==k) 26 return; 27 for(int i = 0; i < 4; ++i) 28 { 29 int tx = x + dir[i][0]; 30 int ty = y + dir[i][1]; 31 if(!islegal(tx, ty)) 32 continue; 33 if(vis[tx][ty] < vis[x][y]) 34 continue; 35 if(i!=di && vis[tx][ty] < vis[x][y]+1) 36 continue; 37 vis[tx][ty] = vis[x][y]; 38 if(i != di) 39 ++vis[tx][ty]; 40 DFS(tx, ty, i); 41 if(flag) 42 return; 43 } 44 } 45 46 int main(void) 47 { 48 #ifdef LOCAL 49 freopen("1728in.txt", "r", stdin); 50 #endif 51 52 int T; 53 scanf("%d", &T); 54 while(T--) 55 { 56 scanf("%d%d", &row, &col); 57 getchar(); 58 for(int i = 0; i < row; ++i) 59 { 60 for(int j = 0; j < col; ++j) 61 { 62 scanf("%c", &map[i][j]); 63 vis[i][j] = MAX; 64 } 65 getchar(); 66 } 67 scanf("%d%d%d%d%d", &k, &sy, &sx, &ey, &ex); 68 --sx, --sy, --ex, --ey; 69 vis[sx][sy] = -1; 70 flag = false; 71 DFS(sx, sy, -1); 72 if(flag) printf("yes\n"); 73 else printf("no\n"); 74 } 75 return 0; 76 }
?
下面重頭戲來了，解法永遠都是只有更好沒有最好。博主講了一個單方向優先擴展的廣搜。
把一般的廣搜比作一個石子在起點激起一圈圈漣漪，單方向優先的就是向開車一樣“橫沖直撞”、直來直往。
因為我們是要找轉彎次數最小的，因此這樣的搜索方式應該也能較快的找到符合條件的路徑，運行時間15MS
感覺代碼的有些小細節還沒有理解透，等以后回過頭來慢慢消化
1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <queue> 6 using namespace std; 7 8 struct Point 9 { 10 int x, y; 11 }cur, next; 12 13 const int MAX = 200; 14 char map[105][105]; 15 int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; 16 int row, col, vis[105][105]; 17 int sx, sy, ex, ey, k; 18 19 bool islegal(int x, int y) 20 { 21 return(x>=0 && x<row && y>=0 && y<col && map[x][y]=='.'); 22 } 23 24 void BFS(void) 25 { 26 queue<Point> qu; 27 vis[sx][sy] = -1; 28 Point cur; 29 cur.x = sx, cur.y = sy; 30 qu.push(cur); 31 while(!qu.empty()) 32 { 33 cur = qu.front(); 34 qu.pop(); 35 if(cur.x==ex&&cur.y==ey&&vis[cur.x][cur.y]<=k) 36 { 37 printf("yes\n"); 38 return; 39 } 40 for(int i = 0; i < 4; ++i) 41 { 42 next = cur; 43 next.x += dir[i][0]; 44 next.y += dir[i][1]; 45 while(islegal(next.x, next.y)) 46 { 47 if(vis[next.x][next.y] < vis[cur.x][cur.y] + 1) 48 break; 49 vis[next.x][next.y] = vis[cur.x][cur.y] + 1; 50 if(vis[next.x][next.y] > k) 51 break; 52 if(vis[next.x][next.y] == k && next.x!=ex && next.y!=ey) 53 break; 54 qu.push(next); 55 next.x += dir[i][0]; 56 next.y += dir[i][1]; 57 } 58 } 59 } 60 printf("no\n"); 61 } 62 63 int main(void) 64 { 65 #ifdef LOCAL 66 freopen("1728in.txt", "r", stdin); 67 #endif 68 69 int T; 70 scanf("%d", &T); 71 while(T--) 72 { 73 scanf("%d%d", &row, &col); 74 getchar(); 75 for(int i = 0; i < row; ++i) 76 { 77 for(int j = 0; j < col; ++j) 78 { 79 scanf("%c", &map[i][j]); 80 vis[i][j] = MAX; 81 } 82 getchar(); 83 } 84 scanf("%d%d%d%d%d", &k, &sy, &sx, &ey, &ex); 85 --sx, --sy, --ex, --ey; 86 BFS(); 87 } 88 return 0; 89 }
?
.doc)
 學習筆記（四）)
