描述
题解
dfs 可解,先初始化全部为墙,也就是 *
,然后我们开始打洞,一直打到起点,判断路径长度是否满足,不满足回溯砌墙就好了,最后一定会生成一个符合条件的洞直达起点。
好题,算是一个比较有趣的问题。
代码
#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 10;
const int DIR[4][2] = {
{
1, 0}, {-1, 0}, {
0, 1}, {
0, -1}};
int n, m;
int x, y, limit;
char map[MAXN][MAXN];
bool dfs(int x, int y, int lim)
{
if (x == 1 && y == 1)
{
return lim >= limit;
}
for (int i = 0; i < 4; i++)
{
int x_ = x + DIR[i][0];
int y_ = y + DIR[i][1];
if (!x_ || !y_ || x_ > n || y_ > m || map[x_][y_] != '*')
{
continue;
}
int cnt = 0;
for (int j = 0; j < 4; j++)
{
int u = x_ + DIR[j][0];
int v = y_ + DIR[j][1];
if (map[u][v] == '.')
{
cnt++;
}
}
if (cnt > 1)
{
continue;
}
map[x_][y_] = '.';
if (dfs(x_, y_, lim + 1))
{
return true;
}
map[x_][y_] = '*';
}
return false;
}
int main()
{
while (cin >> n >> m)
{
cin >> x >> y >> limit;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
map[i][j] = '*';
}
}
map[x][y] = '.';
dfs(x, y, 0);
for (int i = 1; i <= n; i++)
{
puts(map[i] + 1);
}
}
return 0;
}