HDU 2821Pusher（DFS ）

分类：…..|—-高级搜索

HDU2821

题意：是一个游戏，可以玩下，就很清楚了，给你有箱子的图，你现在选择一个初始位置，并确定推的方向序列，规则：你要和箱子至少有一个空格才可以推，每次是先拿掉一个箱子，再把剩余的箱子（如果还存在的话）推向下一格，选择一个方向后要一直沿着这个方向走到不能走为止。

;const int maxn=30;const int inf=9999999;char tmp[maxn][maxn];int n,m;int a[maxn][maxn];int dir[][2]={{1,0},{0,1},{-1,0},{0,-1}};allNum;//所有的箱子数bool pan(int x,int y){if(x>=0&&x<n&&y>=0&&y<m)return true;return false;}bool dfs(int x,int y,int num){if(num==allNum){path[num]=0;return true;}for(int i=0;i<4;i++){int xx=x+dir[i][0];int yy=y+dir[i][1];if(!pan(xx,yy)||a[xx][yy])continue;//判断从（x,y）这一方向出发是否合法，1.在图里，2.不能有箱子while(pan(xx,yy)&&!a[xx][yy]){//沿着这个方向继续探测xx+=dir[i][0];yy+=dir[i][1];}if(!pan(xx,yy))continue;//判断while结束的条件int t=a[xx][yy];a[xx+dir[i][0]][yy+dir[i][1]]+=t-1;path[num]=dirr[i];a[xx][yy]=0;if(dfs(xx,yy,num+1))return true;a[xx+dir[i][0]][yy+dir[i][1]]-=t-1;//回溯把图复原a[xx][yy]=t;}return false;}int main(){while(~scanf(“%d%d”,&m,&n)){allNum=0;for(int i=0;i<n;i++){scanf(“%s”,tmp[i]);for(int j=0;j<m;j++){if(tmp[i][j]>=’a’&&tmp[i][j]<=’z’){allNum+=tmp[i][j]-‘a’+1;a[i][j]=tmp[i][j]-‘a’+1;}else {a[i][j]=0;}}}for(int i=0;i<n;i++){for(int j=0;j<m;j++)if(!a[i][j]&&dfs(i,j,0)){printf(“%d\n%d\n%s\n”,i,j,path);goto A;}}A:;}return 0;}

上一篇HDU 2128Tempter of the Bone II(bfs + 保存每一步的图)下一篇HDU3533Escape（BFS ）

顶0踩0

，世界会向那些有目标和远见的人让路(冯两努——香港着名推销商

相关文章：

你感兴趣的文章：

标签云：