蓝桥真题--路径之谜DFS解法

路径之谜

思路

在这里插入图片描述

前置知识：深度搜索模板
搜索所有可以找的路径，将走过的靶子减去一
走到最后一个格子的时候，直接去判断所有的靶子
只有除最后一个位置的靶子，其余靶子都归零的时候，判断一个最后一个位置横坐标和纵坐标的靶子
如果这两个靶子都是1，是我们要的答案，输出路径
每次走过一个格子，都将对应的坐标存入一个path数组中，回溯时就将他复原回去
对于其他状态也需要进行复原，美名其曰-恢复现场

Coding

#include <iostream>
#include <vector>
using namespace std;
const int N = 21;
int vx[] = {0,0,1,-1};
int vy[] = {1,-1,0,0};
int xba[N];
int yba[N];
int path[N*N];
int n, idx;
bool st[N][N];inline void dfs(int x, int y) {if (x == n-1 && y == n-1) {for (int i = 0; i < n-1; i++) {if (xba[i] || yba[i]) return;}if (xba[n-1] == 1 && yba[n-1] == 1) {path[idx ++] = n*y+x;for (int j = 0; j < idx; j++) {cout << path[j] << ' ';}cout << endl;}}for (int i = 0; i < 4; i++) {int nx, ny;nx = x + vx[i], ny = y + vy[i];if (x >= 0 && y >= 0 && x < n && y < n && !st[x][y]) {st[x][y] = true;xba[x]--;yba[y]--;path[idx ++] = n*y+x;dfs(nx, ny);xba[x]++;yba[y]++;idx--;st[x][y] = false;}}
}int main() {cin >> n;for (int i = 0; i < n; i++) {cin >> xba[i];}for (int i = 0; i < n; i++) {cin >> yba[i];}dfs(0, 0);
}