路径之谜-2016年国赛
- 1、题目描述
- 2、解题思路
- 3、代码实现
1、题目描述
小明冒充 X 星球的骑士，进入了一个奇怪的城堡。
城堡里边什么都没有，只有方形石头铺成的地面。
假设城堡地面是 n×n* 个方格。如下图所示。
按习俗，骑士要从西北角走到东南角。可以横向或纵向移动，但不能斜着走，也不能跳跃。每走到一个新方格，就要向正北方和正西方各射一箭。（城堡的西墙和北墙内各有 n 个靶子）同一个方格只允许经过一次。但不必走完所有的方格。如果只给出靶子上箭的数目，你能推断出骑士的行走路线吗？有时是可以的，比如上图中的例子。
本题的要求就是已知箭靶数字，求骑士的行走路径（测试数据保证路径唯一）
输入描述
第一行一个整数 N (0≤N≤20)，表示地面有个方格。
第二行 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
2、解题思路
看到这种给一个起点和终点走方格的时候，第一反应就应该是DFS或者BFS了，一条路走到黑这种适合DFS，这题很符合。
骑士从左上角起点出发，没走一步，往左边和上边对应位置射一箭，题目在方格的左边和上边给出了骑士从起点到终点射箭的数量，现在让我们求骑士行走的路线。
那我们可以逆向一下，我们从入口开始走，没走一步就将当前位置左边和上边箭的数量减一，如果我们走到了终点且当前所有箭靶上箭的数量为零，则说明我们所走的路线就是骑士经过的路线。
我们设置一个方向
public static int[][] dirs = {
{-1, 0}, //上
{1, 0}, //下
{0, -1}, //左
{0,1} //右
};从起点开始DFS，没走一个新的位置，就要进行判断
- 如果该点是终点，且箭靶上箭的数量为0，则说明走过的路线就是骑士经过的路线，算法结束。
- 如果当前点不是终点，且没有被访问过，那么我们可以用一个path数组记录下该路径，然后继续向上下左右进行DFS。
- 如果走到终点且箭靶上的箭还没有被拔完，那我们就要济宁回溯操作(标记当前点未访问，左边箭靶数量+1，上边箭靶数量+1)。
3、代码实现
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
public class Main {
public static int n;
public static int[] path; //记录路径
public static int[] countLeft; //左边箭靶上的箭
public static int[] countUp; //上边箭靶上的箭
public static boolean[][] visited; //访问标记
public static boolean success=false;//走到终点的标记
public static int[][] dirs={
{-1,0}, //上
{1,0}, //下
{0,-1}, //左
{0,1} //右
};
public static StreamTokenizer st=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
public static void main(String[] args) throws IOException {
n=nextInt();
countLeft=new int[n];
countUp=new int[n];
path=new int[n*n];
visited=new boolean[n][n];
for (int i = 0; i <n; i++) {
countUp[i]=nextInt();
}
for (int i = 0; i <n ; i++) {
countLeft[i]=nextInt();
}
//从起点开始dfs
dfs(0,0,0);
}
public static void dfs(int x, int y, int step) {
path[step]=x*n+y; //将该点编号转变为一维并记录
visited[x][y]=true; //访问标记
countLeft[x]--; //拔掉左边箭靶上的箭
countUp[y]--; //拔掉右边箭靶上的箭
if(x==n-1&&y==n-1&&check()){ //是否到达终点
success=true; //标记已经走到终点
for (int i = 0; i <=step ; i++) {
System.out.print(path[i]+" ");
}
return;
}
for (int[] dir : dirs) { //四个方向搜索
int tmpX=x+dir[0];
int tmpY=y+dir[1];
//没有到达终点且不越界，且(tmpX,tmpY)没有被访问过
if(!success&&tmpX>=0&&tmpX<=n-1&&tmpY>=0&&tmpY<=n-1&&!visited[tmpX][tmpY]){
dfs(tmpX,tmpY,step+1); //搜索下一步
visited[tmpX][tmpY]=false; //复原，回溯
countLeft[tmpX]++;
countUp[tmpY]++;
}
}
}
public static boolean check() { //
for (int i = 0; i < n; i++) {
//到终点的时候箭还没有拔完
if(countLeft[i]!=0||countUp[i]!=0){
return false;
}
}
//到终点时箭刚好拔完
return true;
}
public static int nextInt() throws IOException{
st.nextToken();
return (int)st.nval;
}
}跑一个测试用例看看
数组中记录的是经过的每个方格的编号，最后将这些编号输出即为骑士从起点到终点走过的路径。