http://acm.hdu.edu.cn/showproblem.php?pid=1010
折磨我一下午
题目大意： 从s点走到d点能否恰好走k步 刚开始以为是广搜，其实是深搜。
dfs多优化一下才会过。
#include<stdio.h> #include<stdlib.h> #include<algorithm> #include<math.h> #include<string.h> #include<iostream> #include<queue> #include<ctype.h> using namespace std; #define N 10 #define memset(a,b) memset(a,b,sizeof(a)) #define Lson r<<1|1 #define Rson r<<1 struct node { int x,y,step; }s,e; int n,m,k; int dis[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; int vis[N][N]; char maps[N][N]; int is=0; void dfs(node t) { if(is) return; if(t.x==e.x && t.y==e.y && t.step==k) { is=true; return; } if(t.step>=k) return; int Min=(int)(abs(t.x-e.x)+abs(t.y-e.y)); if(Min>k-t.step) return; if(Min%2!=(k-t.step)%2) return; if(t.x==e.x && t.y==e.y) return; node q; for(int i=0;i<4;i++) { q.x=t.x+dis[i][0]; q.y=t.y+dis[i][1]; q.step=t.step+1; if(is || q.x<0 || q.x>=n || q.y<0 || q.y>=m || maps[q.x][q.y]=='X') continue; if(q.x==e.x && q.y==e.y && q.step==k) { is=true; return; } char ch=maps[q.x][q.y]; maps[q.x][q.y]='X'; dfs(q); maps[q.x][q.y]=ch; } } int main() { while(scanf("%d %d %d",&n,&m,&k),n+m+k) { memset(maps,0); int ans=0; for(int i=0;i<n;i++) { scanf("%s",maps[i]); for(int j=0;j<m;j++) { if(maps[i][j]=='S') { s.x=i; s.y=j; s.step=0; } else if(maps[i][j]=='D') { e.x=i; e.y=j; } else ans++; } } if(k-1>ans) { printf("NO "); continue; } maps[s.x][s.y]='X'; is=0; dfs(s); if(is==true) printf("YES "); else printf("NO "); } return 0; }