旅游网站建设规划方案,科技小报手抄报内容,查询域名注册网站,wordpress 文章分类插件尼玛#xff0c;就因为没发现‘yes’写成‘yrs’。整整让哥找了一个小时的bug。有没有..........此刻#xff0c;内流满面#xff01; 分析#xff1a; 开始以为是单纯的BFS,结果WA无数次#xff01;#xff01; 后来分析后发现是要找到不超过转向次数的转向路径, 最重要…尼玛就因为没发现‘yes’写成‘yrs’。整整让哥找了一个小时的bug。有没有..........此刻内流满面 分析 开始以为是单纯的BFS,结果WA无数次 后来分析后发现是要找到不超过转向次数的转向路径, 最重要的是已经访问的节点不能直接标记为已经访问。因为存在远距离但是转向少的情况,所以要标记上每一个已经访问的点到起点所需要的转弯次数。 #includecstdio //这题和连连看一样走过的点可以再次访问 #includequeue#includecstringusing namespace std;#define inf 1000000 int result; //初始化为0结果能走到就为1char map[105][105];int visit[105][105]; //初始化为inf visit[i][j] 记录走过该点是的最小转弯次数 int fang[4][2]{{0,-1},{0,1},{1,0},{-1,0}};int n,m;struct node{ int x; int y; int d; //记录当前该点的方向 int num;}; void bfs(int k,int x1,int y1,int x2,int y2){ queuenode qu; int i,j; node t,tt; t.xx1; t.yy1; t.d-1; t.num0; visit[x1][y1]0; qu.push(t); while(!qu.empty()) { tqu.front(); qu.pop(); if(t.xx2t.yy2t.numk) { result1; return ; } for(i0;i4;i) { tt.xt.xfang[i][0]; tt.yt.yfang[i][1]; if(t.d-1) tt.num0; else if(t.d!i) tt.numt.num1; else tt.numt.num; tt.di; if(tt.x1||tt.y1||tt.xm||tt.yn) continue; if(map[tt.x][tt.y].tt.numvisit[tt.x][tt.y]) { visit[tt.x][tt.y]tt.num; qu.push(tt); } } }} int main(){ int i,j; int t; int k,x1,y1,x2,y2; scanf(%d,t); while(t--) { scanf(%d%d,m,n); //m行n列 getchar(); for(i1;im;i) { for(j1;jn;j) { scanf(%c,map[i][j]); visit[i][j]inf; } getchar(); } scanf(%d%d%d%d%d,k,y1,x1,y2,x2); result0; bfs(k,x1,y1,x2,y2); if(result1) printf(yes\n); else printf(no\n); } return 0;} 转载于:https://www.cnblogs.com/zhangyabin---acm/archive/2012/04/05/2433691.html
