小记:这题题意开始理解出错了,然后一直WA,TLE,我以为只要在一条水平或垂直线上走就不算转弯次数, 然后就是在每一点可以从各个方向进入,但是必须是不同方向才能入队。我就是认为水平或垂直不算转弯次数,所以一直TLE,对每点保存的是最小需要转弯的次数,最开始我太天真了,直接是以点坐标判重的,后来WA后,想通了。
思路:bfs 每点需要最小的转弯数,判重的方法是对每点记录需要的转弯数,保留最小的,非最小的不需入队。 每个节点记录是从哪个方向来的。
代码简单,看看就可以理清思路了:
#include <iostream> #include <cstdio> #include <cstring> #include <queue> using namespace std; const int MAX_ = 10001; const int INF = 100000000; int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; int n,m,cnt; int f[101][101]; int num[101][101]; struct point { int x,y,step; int pre; } s,e,t; void bfs() { queue<point>q; q.push(s); while(!q.empty()) { point cur, next; cur = q.front(); q.pop(); if(cur.x == t.x && cur.y == t.y)return ; for(int i = 0; i < 4; ++i) { next.x = cur.x + dir[i][0]; next.y = cur.y + dir[i][1]; next.step = cur.step; next.pre = i; if((next.x >= 1 && next.x <= n) && (next.y >= 1 && next.y <= m) &&(f[next.x][next.y] != 1)) { if(cur.pre != -1 && cur.pre != i) {// next.step ++; } if(next.step > cnt)continue;//两步很重要 if(num[next.x][next.y] >= next.step) { num[next.x][next.y] = next.step; q.push(next); } } } } } int main() { int T; char c; cin>>T; while(T--) { cin>>n>>m; for(int i = 1; i <= n; ++i) { for(int j = 1; j <= m; ++j) { cin>>c; c == '.'?f[i][j] = 0:f[i][j] = 1; num[i][j] = INF; } } cin>>cnt>>s.y>>s.x>>t.y>>t.x; s.pre = -1; s.step = 0; num[s.x][s.y] = 0; bfs(); if(num[t.x][t.y] <= cnt)cout<<"yes"; else cout<<"no"; cout<<endl; } return 0; }