本文主要是介绍Pusher HDU - 2821(DFS)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Pusher
题目链接：HDU - 2821题意：给出一个R*C的格子， 每个格子中， '.'表示为空，小写字母x表示在这个格子中有x-'a'+1个板子；
选一个初始位置， 推板子， 当与板子不直接相邻时， 可以移掉该方向上的最近的一堆板子上的一个板子， 并将这堆板子向后推一格， 问选那个初始位置可以将板子都清除， 并输出操作；每次移动只能直线移动不撞板子不回头；
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
int R, C;
char G[30][30];
struct node{int pre;char op;
};
int G0[30][30];
char path[2000];
int sum;
int dir[4][2]={1, 0, 0, 1, 0, -1, -1, 0};
char op[]={'D', 'R', 'L', 'U'};
int judge(int x, int y){if(x<0||y<0||x>=R||y>=C) return 0;return 1;
}
int dfs(int x, int y, int num){if(num==sum){path[num]='\0';return 1;}for(int i=0; i<4; i++){int tx, ty;tx=x+dir[i][0];ty=y+dir[i][1];if(!judge(tx, ty)||G0[tx][ty]) continue;while(judge(tx, ty)&&!G0[tx][ty]){tx+=dir[i][0];ty+=dir[i][1];}if(!judge(tx, ty)) continue;int t=G0[tx][ty];G0[tx+dir[i][0]][ty+dir[i][1]]+=t-1;G0[tx][ty]=0;path[num]=op[i];if(dfs(tx, ty, num+1)) return 1;G0[tx][ty]=t;G0[tx+dir[i][0]][ty+dir[i][1]]-=t-1;}return 0;
}
int main(){while(~scanf("%d%d", &C, &R)){sum=0;for(int i=0; i<R; i++){scanf("%s", G[i]);for(int j=0; j<C; j++){if(G[i][j]=='.') G0[i][j]=0;else G0[i][j]=G[i][j]-'a'+1, sum+=G0[i][j];}}int flag=0;for(int i=0; i<R; i++){for(int j=0; j<C; j++){if(!G0[i][j]&&dfs(i, j, 0)){printf("%d\n%d\n%s\n", i, j, path);flag=1;break;}}if(flag) break;}} return 0;
}这篇关于Pusher HDU - 2821(DFS)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
