題意：說有一個人推箱子，每次推時他要和箱子間隔一個空格子，一個格子上有x個箱子，則這些箱子會消失一個，另外n-1個推到了相鄰格子的地方。

思路：首先，遍歷整個圖嘗試每個格子，若能開始則一直走到邊界或碰到箱子為止，只有碰到箱子時才記錄路徑。特別注意記錄方向！

#include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> #include<queue> #include<map> using namespace std; #define N 30 #define ll long long const int inf=0x7fffffff; int n,m,sum; char str[N][N]; char path[N*N]; char ch[10]={"URDL"}; int g[N][N]; int dir[4][2]={-1,0,0,1,1,0,0,-1}; bool judge(int x,int y) {if(x>=0&&x<m&&y>=0&&y<n)return true;return false; } bool dfs(int x,int y,int cnt) {int i,di,dj;if(cnt==sum){path[cnt]='\0';return true;}for(i=0;i<4;i++){di=x+dir[i][0];dj=y+dir[i][1];if(g[di][dj])continue;while(g[di][dj]==0){di+=dir[i][0];dj+=dir[i][1];}if(!judge(di,dj))continue;int tmp=g[di][dj];g[di][dj]=0;g[di+dir[i][0]][dj+dir[i][1]]+=tmp-1;path[cnt]=ch[i];if(dfs(di,dj,cnt+1))return true;g[di][dj]=tmp;g[di+dir[i][0]][dj+dir[i][1]]-=tmp-1;}return false; } int main() {int i,j;while(scanf("%d%d",&n,&m)!=-1){for(i=sum=0;i<m;i++){scanf("%s",str[i]);for(j=0;j<n;j++){if(str[i][j]=='.')g[i][j]=0;elseg[i][j]=str[i][j]-'a'+1;sum+=g[i][j];}}for(i=0;i<m;i++){for(j=0;j<n;j++){if(!g[i][j]&&dfs(i,j,0))break;}if(j<n)break;}printf("%d\n%d\n",i,j);puts(path);}return 0; }

　　

?

轉載于:https://www.cnblogs.com/walker11/p/4356979.html

總結

以上是生活随笔為你收集整理的hdu 2821 Pusher （dfs）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。