题目
小明冒充 星球的骑士，进入了一个奇怪的城堡。
城堡里边什么都没有，只有方形石头铺成的地面。
假设城堡地面是 个方格，如下图所示。
按习俗，骑士要从西北角走到东南角。
可以横向或纵向移动，但不能斜着走，也不能跳跃。
每走到一个新方格，就要向正北方和正西方各射一箭。（城堡的西墙和北墙内各有 个靶子）
同一个方格只允许经过一次。
但不必走完所有的方格。
如果只给出靶子上箭的数目，你能推断出骑士的行走路线吗？
有时是可以的，比如上图中的例子。
本题的要求就是已知箭靶数字，求骑士的行走路径。
输入格式
第一行一个整数 ，表示地面有 个方格。
第二行 个整数，空格分开，表示北边的箭靶上的数字（自西向东）。
第三行 个整数，空格分开，表示西边的箭靶上的数字（自北向南）。
输出格式
一行若干个整数，表示骑士路径。
为了方便表示，我们约定每个小格子用一个数字代表，从西北角开始编号: 。
任意合理答案均可。
比如，图例中的方块编号为：
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
数据范围
输入样例：
4
2 4 3 4
4 3 3 3
输出样例：
0 4 5 1 2 3 7 11 10 9 13 14 15
解题
方法一：DFS 回溯
思路
经典的爆搜+回溯+剪枝题，从左上角开始搜索，每次尝试上下左右四个方向，坐标越界或者西墙或北墙的箭数不够时剪枝并回溯，最后搜索到右下角的时判断如果找到了正确的路径就输出并直接退出程序。
代码
import java.util.*;
import java.io.*;
public class _路经之谜 {
// 上右下左四个方向
static final int[][] DIRECTIONS = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
static int n; // 城堡边长
static int[] rows, cols; // rows西墙 cols左墙
static boolean[] vis; // 标识每个格子是否已经被访问过了
static Deque<Integer> path = new LinkedList<>(); // 双端队列用于存路径
// 为什么要用双端队列？
// 路径增加时要往队尾追加元素，回溯时要从队尾删除元素，但输出路径时要从队头开始遍历
static boolean hasAns = false; // 标识是否已经找到答案
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
in.nextToken();
n = (int) in.nval;
rows = new int[n];
cols = new int[n];
for (int i = 0; i < n; ++i) {
in.nextToken();
cols[i] = (int) in.nval;
}
for (int i = 0; i < n; ++i) {
in.nextToken();
rows[i] = (int) in.nval;
}
vis = new boolean[n * n];
// 输入结束 开始深搜
dfs(0, 0);
}
static void dfs(int x, int y) {
if (hasAns) return; // 如果已经找到答案就直接退出
--rows[x]; // 把西墙和北墙上的箭减少
--cols[y];
int curr = x * n + y; // 当前格子的序号
vis[curr] = true; // 标识该格子已经访问过
path.offer(curr); // 路径增加
// 如果当前已经走到了右下角
if (curr == n * n - 1) {
// 判断西墙或北墙上的箭是否都已经清空为0
for (int i = 0; i < n; ++i) {
if (rows[i] != 0 || cols[i] != 0) return;
}
// 都已清空就说明找到了一个合法的解 输出
StringBuilder ans = new StringBuilder();
while (!path.isEmpty()) {
ans.append(" ").append(path.poll());
}
System.out.println(ans.substring(1));
hasAns = true; // 答案已经找到了
return;
}
// 遍历四个方向
for (int[] d : DIRECTIONS) {
int nx = x + d[0], ny = y + d[1]; // 新的坐标
int next = nx * n + ny; // 新坐标的序号
// 剪枝：越界或者s已经走过这个格子或者墙上的箭数为负
if (nx < 0 || nx >= n || ny < 0 || ny >= n ||
vis[next] || rows[nx] <= 0 || cols[ny] <= 0) continue;
// 向更深的一层搜索
dfs(nx, ny);
// 回溯
vis[next] = false;
path.pollLast();
++rows[nx];
++cols[ny];
}
}
}
#include <iostream>
#include <queue>
using namespace std;
const int MAX_N = 25;
const int DIRECTIONS[][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
int n;
int rows[MAX_N], cols[MAX_N];
bool vis[MAX_N * MAX_N];
deque<int> path;
void dfs(int x, int y) {
--rows[x], --cols[y];
if (rows[x] < 0 || cols[y] < 0) return;
int curr = x * n + y;
vis[curr] = true;
path.push_back(curr);
if (curr == n * n - 1) {
for (int i = 0; i < n; ++i) {
if (rows[i] != 0 || cols[i] != 0) return;
}
while (!path.empty()) {
printf("%d", path.front());
path.pop_front();
printf(path.empty() ? "\n" : " ");
}
exit(0);
}
for (auto d : DIRECTIONS) {
int nx = x + d[0], ny = y + d[1];
int next = nx * n + ny;
if (nx < 0 || nx >= n || ny < 0 || ny >= n ||
vis[next] || rows[nx] <= 0 || cols[ny] <= 0) continue;
dfs(nx, ny);
vis[next] = false;
path.pop_back();
++rows[nx], ++cols[ny];
}
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i) scanf("%d", &cols[i]);
for (int i = 0; i < n; ++i) scanf("%d", &rows[i]);
dfs(0, 0);
return 0;
}
评论区