hdu 2821

题意：n*m的格子上有一些方块放在某些格子上，一个格子可能有几个方块，用'a'-'z'来表示方块数量。

初始的时候可以选择任意空地作为Pusher初始点，Pusher选择一个方向，然后向这个方向前进直到遇到有方块的格子，Pusher把这个格子的方块清除一个，并把它向前推一格（向前不能出界），如果前面一格有方块，那么这些方合起来放在这个格子中。Pusher和有方块的格子之间至少要有一个空地才能推动。

思路：这道题数据量比较小，直接dfs即可，不过要注意的是回溯的时候要注意把修改的状态复原，其次就是机器人的行走路径，遇到箱子或者出界才能转弯，然后就是几个限制条件，按照题意很容易处理。。最后就是起始位置不能够有方块，不然WA。。。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int r,c,s,flag;
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
char map[25][25],road[1000],d[5] = {"DURL"};

bool check(int x,int y)
{
	if(x < 0 || x >= r || y < 0 || y >= c) return false;
	return true;
}

void dfs(int x,int y,int num)	//表示出发位置为(x,y),已经消灭了num个箱子
{
	if(num >= s)
	{
		road[num] = 0;
		flag = 1;
		return;
	}
	for(int k = 0; k < 4; k++)
	{
		int i = x + dir[k][0];
		int j = y + dir[k][1];
		if(!check(i,j) || map[i][j]) continue;  //下一步就走出界外，或者与箱子之间没有空格
		while(check(i,j) && !map[i][j])
			i += dir[k][0], j += dir[k][1];
		if(!check(i + dir[k][0],j + dir[k][1])) continue;  //到达棋盘边缘，不能推
		int t = map[i][j];
		map[i+dir[k][0]][j+dir[k][1]] += t - 1;
		map[i][j] = 0;
		road[num] = d[k];
		dfs(i,j,num+1);
		if(flag) return;
		map[i+dir[k][0]][j+dir[k][1]] -= t - 1;
		map[i][j] = t;
	}
}

int main()
{
	while(scanf("%d%d",&c,&r)!=EOF)
	{
		s = flag = 0;
		for(int i = 0; i < r; i++)
		{
			getchar();
			scanf("%s",map[i]);
			for(int j = 0; j < c; j++)
			{
				if(map[i][j] == '.') map[i][j] = 0;
				else map[i][j] -= 'a' - 1;
				s += map[i][j];
			}
		}
		for(int i = 0; i < r; i++)
		{
			if(flag) break;
			for(int j = 0; j < c; j++)
			{
				if(map[i][j]) continue;
				dfs(i,j,0);
				if(flag == 1)
				{
					printf("%d\n%d\n",i,j);
					printf("%s\n",road);
					break;
				}
			}
		}
	}
	return 0;
}