原题链接:http://acm.hdu.edu.cn/showproblem.php?pid=2821
首先,题目描述给的链接游戏很好玩,建议先玩几关,后面越玩越难,我索性把这道题A了,也就相当于通关了。
其实这道题算是比较水点搜索题,直接DFS + 回溯,但是题目描述不是很清楚使得很难下手,后来枚举题意才知道在边缘位置不会出现嵌套盒子,而且所有输入都肯定有解决的方案,所有的输入数据都是标准的。
#include <stdio.h>
#include <string.h>
#include <string>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <iostream>
#include <stack>
using namespace std;
const int maxn = ; int dr[][] = {{, }, {-, }, {, }, {, -}};
char dd[] = {'R', 'L', 'D', 'U'};
char g[maxn][maxn];
char path[ * * ];
int a[maxn][maxn];
int r, c;
bool ok(int x, int y)
{
if(x >= && x < c && y >= && y < r && a[y][x] == )
return true;
return false;
} int dfs(int cy, int cx, int cnt, int len)
{
if(len == cnt)
return ;
for(int k = ; k < ; k++)
{
int x = cx + dr[k][];
int y = cy + dr[k][];
if(ok(x, y))
{
do
{
x += dr[k][];
y += dr[k][];
}
while(ok(x, y));
if(x >= && x < c && y >= && y < r)
{
int tmp = a[y][x];
a[y + dr[k][]][x + dr[k][]] += a[y][x] - ;
a[y][x] = ;
path[len] = dd[k];
if(dfs(y, x, cnt, len+))
return ;
path[len] = '\0';
a[y][x] = tmp;
a[y + dr[k][]][x + dr[k][]] -= a[y][x] - ;
}
} }
return ;
} int main()
{
int cnt;
while(scanf("%d %d", &c, &r) != EOF)
{
cnt = ;
for(int i = ; i < r; i++)
{
scanf("%s", g[i]);
for (int j = ; j < c; j++)
{
if(g[i][j] != '.')
cnt += g[i][j] - 'a' + , a[i][j] = g[i][j] - 'a' + ;
else
a[i][j] = ;
}
}
int i, j;
bool flag = false;
for(i = ; i < r; i++)
{
for(j = ; j < c; j++)
{
if(a[i][j] == && dfs(i, j, cnt, ))
{
flag = true;
break;
}
}
if(flag) break;
}
printf("%d\n%d\n", i, j);
for(int i = ; i < cnt; i++) putchar(path[i]);
putchar('\n');
}
return ;
}