0条评论
还没有人评论过~
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 19687 Accepted Submission(s): 4796
1 #include <queue> 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 using namespace std; 6 const int INF = 0x3f3f3f3f; 7 int ac[4][2] = {0, 1, 0, -1, -1, 0, 1, 0}; 8 int r, c, sx, sy, ex, ey, t, k; 9 char map[110][110]; int vis[110][110]; 10 struct pos 11 { 12 int x, y; 13 }; 14 void Bfs () 15 { 16 int i, j; 17 for(i = 0; i < r; i++) 18 for(j = 0; j < c; j++) 19 vis[i][j] = INF; 20 pos ft, tp; 21 ft.x = sx; ft.y = sy; 22 vis[ft.x][ft.y] = -1; 23 queue<pos> q; 24 q.push(ft); 25 while(!q.empty()) 26 { 27 ft = q.front(); 28 q.pop(); 29 if(ft.x == ex && ft.y == ey && vis[ft.x][ft.y] <= k) 30 { 31 puts("yes"); 32 return; 33 } 34 for(int i = 0; i < 4; i++) 35 { 36 tp.x = ft.x + ac[i][0]; 37 tp.y =ft.y + ac[i][1]; 38 while (!(tp.x < 0 || tp.y < 0 || tp.x >= r || tp.y >= c)) 39 { 40 if (map[tp.x][tp.y] == '*') 41 break; 42 if (vis[tp.x][tp.y] < vis[ft.x][ft.y] + 1) 43 break; 44 vis[tp.x][tp.y] = vis[ft.x][ft.y] + 1; 45 if (vis[tp.x][tp.y] > k) 46 break; 47 if (vis[tp.x][tp.y] == k && tp.x != ex && tp.y != ey) 48 break; 49 q.push (tp); 50 tp.x += ac[i][0]; 51 tp.y += ac[i][1]; 52 } 53 } 54 } 55 puts("no"); 56 } 57 int main() 58 { 59 int t, i; 60 scanf("%d", &t); 61 while(t--) 62 { 63 scanf("%d %d", &r, &c); 64 for(i = 0; i < r; i++) 65 cin >> map[i]; 66 67 scanf("%d %d %d %d %d", &k, &sy, &sx, &ey, &ex); 68 sx--; sy--; ey--; ex--; 69 Bfs(); 70 } 71 return 0; 72 }
//懵了。
来源:https://www.cnblogs.com/soTired/p/4723847.html