http://acm.hdu.edu.cn/showproblem.php?pid=1728
这两道题花了一下午的时候调试，因为以前做过类似的题，但是判断方向的方法是错的,一直没发现啊,真无语。
每个状态除了坐标外还需要记录步数,和方向。还要注意输入格式。
并且每一个点并不是走过了就不能在走,只要到达这个点的时候转向次数少的就可以更新这个点，可以等于。千万注意这个坑。
1 #include <cstdio> 2 #include <cstring> 3 #include <queue> 4 using namespace std; 5 int n,m,k; 6 int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}}; 7 char mp[110][110]; 8 int used[110][110]; 9 struct point 10 { 11 int x,y,d,time; 12 bool operator < (const point a) const 13 { 14 return time>a.time; 15 } 16 }; 17 void bfs(int x1,int y1,int x2,int y2) 18 { 19 //printf("%d %d %d %d ",x1,y1,x2,y2); 20 for(int i=0;i<=n;i++) 21 for(int j=0;j<=m;j++) used[i][j]=1<<29; 22 priority_queue<point>que; 23 point s; 24 s.x=x1,s.y=y1,s.d=-1,s.time=0; 25 que.push(s); 26 used[s.x][s.y]=0; 27 while(!que.empty()) 28 { 29 point e=que.top(); que.pop(); 30 printf("%d %d %d ",e.x,e.y,e.time); 31 if(e.time>k) continue; 32 if(e.x==x2&&e.y==y2) {printf("yes ");return;} 33 for(int i=0;i<4;i++) 34 { 35 s.x=e.x+dir[i][0]; 36 s.y=e.y+dir[i][1]; 37 if(s.x<0||s.x>=n||s.y<0||s.y>=m||mp[s.x][s.y]=='*') continue; 38 s.d=i; 39 if(s.d!=e.d&&e.d!=-1) //转向次数加1 并且保证不会往回走构成死循环 40 { 41 s.time=e.time+1; 42 } 43 else s.time=e.time; 44 if(s.time<=used[s.x][s.y]&&s.time<=k) //注意 45 { 46 used[s.x][s.y]=s.time; 47 que.push(s); 48 } 49 } 50 } 51 printf("no "); 52 } 53 54 int main() 55 { 56 freopen("a.txt","r",stdin); 57 int t,x1,y1,x2,y2; 58 scanf("%d",&t); 59 while(t--) 60 { 61 scanf("%d%d",&n,&m); 62 getchar(); 63 for(int i=0;i<n;i++) 64 scanf("%s",&mp[i]); 65 scanf("%d",&k); 66 scanf("%d%d%d%d",&y1,&x1,&y2,&x2); 67 //printf("%d %d %d %d ",x1-1,y1-1,x2-1,y2-1); 68 bfs(x1-1,y1-1,x2-1,y2-1); 69 } 70 return 0; 71 }
知道写bfs了 换成dfs还是挺容易的。
并且bfs是1400ms,dfs只有31ms。
#include <cstdio> #include <cstring> char mp[110][110]; int n,m,k; int dir[4][2]={{-1,0},{1,0},{0,1},{0,-1}}; int x2,y2; bool flag; int vis[110][110]; void dfs(int x,int y,int d,int step) { //printf("%d %d %d %d ",x,y,d,step); if(flag) return; if(x==x2&&y==y2&&step<=k) { flag=1; printf("yes "); return; } for(int i=0;i<4;i++) { int xx=x+dir[i][0]; int yy=y+dir[i][1]; int dd=i; if(xx>=0&&xx<n&&yy>=0&&yy<m&&mp[xx][yy]!='*') { int s=step; if(d!=dd&&d!=-1) s++; if(s<=vis[xx][yy]&&s<=k) //强力的剪枝 { vis[xx][yy]=s; dfs(xx,yy,dd,s); } } } } int main() { // freopen("a.txt","r",stdin); int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(int i=0;i<n;i++) scanf("%s",mp[i]); int x1,y1; scanf("%d%d%d%d%d",&k,&y1,&x1,&y2,&x2); flag=0; for(int i=0;i<=n;i++) for(int j=0;j<m;j++) vis[i][j]=1<<29; x1--,y1--; x2--,y2--; vis[x1][y1]=0; dfs(x1,y1,-1,0); if(!flag) printf("no "); } return 0; }
http://acm.hdu.edu.cn/showproblem.php?pid=1175
这个题的坑点在于只能两个端点是非0数,不能经过其他的数字。
思路是一样的。
#include <cstdio> #include <cstring> #include <queue> using namespace std; int n,m; int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}}; int mp[1010][1010]; int used[1010][1010]; struct point { int x,y,d,time; bool operator < (const point a) const { return time>a.time; } }; point t; bool bfs(point s) { for(int i=0;i<=n;i++) for(int j=0;j<=m;j++) used[i][j]=1<<29; priority_queue<point>que; que.push(s); used[s.x][s.y]=0; while(!que.empty()) { point e=que.top(); que.pop(); if(e.x==t.x&&e.y==t.y) return true; for(int i=0;i<4;i++) { s.x=e.x+dir[i][0]; s.y=e.y+dir[i][1]; s.d=i; if(s.x<1||s.x>n||s.y<1||s.y>m) continue; if(mp[s.x][s.y]!=0&&(s.x!=t.x||s.y!=t.y)) continue; //注意别逻辑别写错了 //printf("%d %d %d ",s.x,s.y,s.time); if(s.d!=e.d&&e.d!=-1) s.time=e.time+1; else s.time=e.time; if(s.time<=used[s.x][s.y]&&s.time<=2) { used[s.x][s.y]=s.time; que.push(s); } } } return false; } int main() { //freopen("a.txt","r",stdin); int q,x1,y1,x2,y2; while(~scanf("%d%d",&n,&m)) { if(n==0&&m==0) break; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&mp[i][j]); scanf("%d",&q); while(q--) { scanf("%d%d%d%d",&x1,&y1,&x2,&y2); if(!mp[x1][y1]||mp[x1][y1]!=mp[x2][y2]) printf("NO "); else { point s; s.x=x1,s.y=y1,s.d=-1,s.time=0; t.x=x2,t.y=y2; if(bfs(s)) printf("YES "); else printf("NO "); } } } return 0; }