蓝桥云客路径之谜

11.路径之谜 - 蓝桥云课 路径之谜 题目描述

小明冒充X星球的骑士，进入了一个奇怪的城堡。 城堡里边什么都没有，只有方形石头铺成的地面。 假设城堡地面是n×n个方格。如下图所示。

按习俗，骑士要从西北角走到东南角。可以横向或纵向移动，但不能斜着走，也不能跳跃。每走到一个新的方格，就要向正北方和正西方各射一箭。(城堡的西墙和北墙内各有n个靶子)同一个方格只允许经过一次。但不必走完所有的方格。如果只给出靶子上箭的数目，你能推断出骑士的行走路线吗？有时是可以的，比如上图中的例子。

本题的要求就是已知箭靶数字，求骑士的行走路径(测试数据保证路径唯一)

输入描述 第一行一个整数N (0 ≤ N ≤ 20)，表示地面有N×N个方格。第二行N个整数，空格分开，表示北边的箭靶上的数字（自西向东）第三行N个整数，空格分开，表示西边的箭靶上的数字（自北向南） 输出描述

输出一行若干个整数，表示骑士路径。 为了方便表示，我们约定每个小格子用一个数字代表，从西北角开始编号：0,1,2,3… 比如，上图中的方块编号为： 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

运行限制 ● 最大运行时间：5s ● 最大运行内存：256M

总通过次数：8429 | 总提交次数：10910 | 通过率：77.3%

难度：困难 标签：2016，国赛，DFS

思路：

凭借题目给的要求纯暴力就好

代码如下：   #include<iostream> #include<algorithm> #include<vector> using namespace std; int n; int yl[30],xl[30]; int dx[] = {0,1,0,-1}; int dy[] = {1,0,-1,0}; bool vis[30][30]; vector <int> arr; bool found = false; void dfs(int x,int y,int xv,int yv) { if(found) return; if(x == n-1 && y == n-1) { if(xv == 0 && yv == 0) { found = true; for(int i = 0 ; i < arr.size() ; i++) cout << arr[i] << " "; } return ; } for(int k = 0 ; k < 4 ; k++) { int tx = x + dx[k]; int ty = y + dy[k]; if(tx >= 0 && ty >= 0 && tx < n && ty < n && !vis[tx][ty]) { if(yl[ty] && xl[tx]) { vis[tx][ty] = true; xl[tx]--; yl[ty]--; xv--; yv--; arr.push_back(tx*n+ty); dfs(tx,ty,xv,yv); arr.pop_back(); vis[tx][ty] = false; xl[tx]++; yl[ty]++; xv++; yv++; } } } } int main() { cin >> n; int yv = 0,xv = 0; for(int i = 0 ; i < n ; i++) { cin >> yl[i]; yv += yl[i]; } for(int i = 0 ; i < n ; i++) { cin >> xl[i]; xv += xl[i]; } vis[0][0] = true; arr.push_back(0); xl[0]--; yl[0]--; yv--; xv--; dfs(0,0,xv,yv); return 0; }