2016蓝桥杯C++A组路径之谜参考代码

之前在网上看到的多是Java 但是我没学过Java..... 找了一篇C的，调了很久很久很久.......

城堡里边什么都没有，只有方形石头铺成的地面。
假设城堡地面是 n x n 个方格。【如图1.png】所示。


按习俗，骑士要从西北角走到东南角。
可以横向或纵向移动，但不能斜着走，也不能跳跃。
每走到一个新方格，就要向正北方和正西方各射一箭。
（城堡的西墙和北墙内各有 n 个靶子）
同一个方格只允许经过一次。但不必走完所有的方格。
如果只给出靶子上箭的数目，你能推断出骑士的行走路线吗？
有时是可以的，比如图1.png中的例子。
本题的要求就是已知箭靶数字，求骑士的行走路径（测试数据保证路径唯一）
输入：
第一行一个整数N(0<N<20)，表示地面有 N x N 个方格
第二行N个整数，空格分开，表示北边的箭靶上的数字（自西向东）
第三行N个整数，空格分开，表示西边的箭靶上的数字（自北向南）
输出：
一行若干个整数，表示骑士路径。
为了方便表示，我们约定每个小格子用一个数字代表，从西北角开始编号: 0,1,2,3....
比如，图1.png中的方块编号为：
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

代码如下：

1. #include "stdafx.h"  
2. #include <iostream>  
3. using namespace std;  
4.   
5.   
6. int N;  
7. const int max = 20;  
8. int west[max];  
9. int north[max];  
10. int pic[max][max];  
11. int iv[400];  
12. int dicx[] = { 1,-1,0,0 };  
13. int dicy[] = { 0,0,1,-1 };  
14. int ans[400];  
15. int num;  
16. bool ok = false;  
17.   
18.   
19. bool isin(int x,int y)  
20. {  
21.     if (x < N && x >= 0 && y < N && y >= 0)  
22.     {  
23.         return true;  
24.     }  
25.     else  
26.     {  
27.         return false;  
28.     }  
29. }  
30. bool J()  
31. {  
32.     for (int i = 0; i < N; i++)  
33.     {  
34.         if (north[i] != 0)  
35.             return false;  
36.     }  
37.     for (int i = 0; i < N; i++)  
38.     {  
39.         if (west[i] != 0)  
40.             return false;  
41.     }  
42.     return true;  
43. }  
44. bool isr(int x, int y)  
45. {  
46.     if (west[y] >= 0 && north[x] >= 0)  
47.     {  
48.         return true;  
49.     }  
50.     else  
51.     {  
52.         return false;  
53.     }  
54. }  
55. void dfs(int x,int y,int l)  
56. {  
57.     if (pic[y][x] == N * N - 1 )//终止条件  
58.     {  
59.         if (J())  
60.         {  
61.             ans[l] = pic[y][x];  
62.             ok = true;  
63.             num = l;  
64.             return;  
65.         }  
66.         else   
67.         {  
68.             return;  
69.         }  
70.     }  
71.     if (isin(x, y) && !(bool)iv[pic[y][x]] && isr(x,y))//判断当前位置是否符合条件 1.在图内 2.未经过 3.可以经过  
72.     {  
73.         iv[pic[y][x]] = 1;//尝试  
74.         ans[l] = pic[y][x];  
75.         for (int i = 0; i < 4; i++)//判断当前位置能否继续求解  
76.         {  
77.             int y_tem = y + dicy[i];  
78.             int x_tem = x + dicx[i];  
79.             if (isin(x_tem, y_tem) && !(bool)iv[pic[y_tem][x_tem]] && north[x_tem] - 1 >=0 && west[y_tem] - 1 >= 0)  
80.             {  
81.                 north[x_tem] = north[x_tem] - 1;//尝试  
82.                 west[y_tem] = west[y_tem] - 1;  
83.                 dfs(x_tem, y_tem, l + 1);  
84.                 if (ok) return;  
85.                 north[x_tem] = north[x_tem] + 1;//撤销  
86.                 west[y_tem] = west[y_tem] + 1;  
87.             }  
88.         }  
89.         iv[pic[y][x]] = 0;//撤销    
90.         return;  
91.     }  
92.     else  
93.         return;  
94. }  
95.   
96. int main()  
97. {  
98.     cin >> N;  
99.   
100.     for (int i = 0; i < N; i++)  
101.     {  
102.         cin >> north[i];  
103.     }  
104.     for (int i = 0; i < N; i++)  
105.     {  
106.         cin >> west[i];  
107.     }  
108.     int k = 0;  
109.     for (int i = 0; i < N; i++)  
110.     {  
111.         for (int n = 0; n < N; n++)  
112.         {  
113.   
114.             pic[i][n] = k;  
115.             k++;  
116.         }  
117.     }  
118.     for (int i = 0;i < 400; i++)  
119.     {  
120.         iv[i] = 0;  
121.     }  
122.     west[0]--;  
123.     north[0]--;  
124.     dfs(0, 0, 0);  
125.     for (int i = 0; i<= num; i++)  
126.     {  
127.         cout << ans[i] << " ";  
128.     }  
129.       
130.   
131.     system("pause");  
132.     return 0;  
133. }