#include<stdio.h> #include<stdlib.h> #include<string.h> int n,m,k,x1,y1,x2,y2,vis[110][110]; int fx[4][2]={{1,0},{-1,0},{0,-1},{0,1}}; char hash[101][101]; struct node { int x,y;//x表示列，y表示行 int turn;//转弯的次数 }q[100100],s,next; int pd(int x,int y) { if(x<0||x>=n||y<0||y>=m) return 0; return 1; } int bfs() { int head,tail,w,x,y,i; memset(vis,0,sizeof(vis)); x1--; y1--; x2--; y2--; s.x=x1; s.y=y1; s.turn=-1; head=tail=0; q[head]=s; vis[y1][x1]=1; while(head<=tail) { s=q[head++]; if(s.x==x2&&s.y==y2&&s.turn<=k) return 1; next.turn=s.turn+1;//因为前面搜完了一个方向，就肯定会拐弯，所以要+1，也因此起点的turn初始化为-1; for(i=0;i<4;i++) { y=s.y+fx[i][0]; x=s.x+fx[i][1]; //if() while(pd(x,y)&&hash[y][x]=='.') { if(vis[y][x]==0)//这里的标志是标志出转弯最少的各个位置上的是否访问 { vis[y][x]=1; next.x=x; next.y=y; q[++tail]=next; } y+=fx[i][0]; x+=fx[i][1]; } //printf("dian(%d %d),turn %d ",t.y,t.x,t.turn); } } return 0; } int main() { int t,i,j; char test[10]; scanf("%d",&t); gets(test); while(t--) { scanf("%d%d",&m,&n); gets(test); for(i=0;i<m;i++) gets(hash[i]); //gets(test); scanf("%d%d%d%d%d",&k,&x1,&y1,&x2,&y2);//x是列，y是行 i=bfs(); if(i) printf("yes "); else printf("no "); } //system("pause"); return 0; }
http://acm.hdu.edu.cn/showproblem.php?pid=1728
这题刚开始按普通的方法去做，结果一直wa，原来是普通的方法是以时间或步骤数为基准去找寻答案，而这题的限制条件在于转弯的次数，所以应以转弯的次数去逐次遍历
每次都将一个方向上的格子走完并存入队列，之后并表示该格子已经走过，这样可以保证走过的格子都是转弯次数最少的。
做了这题还学习了方向可以这样表示的int fx[4][2]={{1,0},{-1,0},{0,-1},{0,1}};，很少用到向量，但这确实很管用，代码比八数码少了很多
另外，还有在广搜时的限制条件是关键，也有用dfs写了，不过因为还有些地方不知道如何剪枝，所以一直在超时中