网站首页 > 精选教程 正文

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

输入：

第一行一个整数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

解题思路：一开始从0,0这个坐标开始，可以向右，也可以向下。一个立足点，可以向上，向左，向右，向下四个方向前进，直到n-1,n-1坐标退出，每走到一格对应的列、行数组+1。退出后核对列数组每个值是否和输入要求一致，行数组每个值是否和输入要求一致，如果一致算一个路径方法。

代码：

public class LuJin {

public static void main(String[] args){

doit(4,new int[]{2,4,3,4},new int[]{4,3,3,3});//题目中的测试数据，用于验证

}

static void doit(int num,int[] top, int[] left){

int ctop[] = new int[num]; //初始化列靶子数组，长度和格子列数一样，用来记录累计的箭

Arrays.fill(ctop,0);

int cleft[] = new int[num];//初始化行靶子数组，长度和格子行数一样，用来记录累计的箭

Arrays.fill(cleft,0);

doit1(0,num,top,left,ctop,cleft,"");//递归寻路，从0开始，我把n*n格子看层（n*n）*1的一行数组，num是n值，“”是要记录走过的点位置

}

/**

* p 从0开始

* @param p

* @param num

* @param trace 记录走过的点用“，”分隔

*/

static void doit1(int p,int num,int stop[], int sleft[],int ctop[],int[] cleft,String trace){

int lnum = p/num; //当前行数

int cnum = p%num; //当前列数

int top = p-num; //当前点上一行对应的位置

int left = p-1;//当前行左边的位置

int right = p+1;//当前行右边的位置

int down = p+num;//当前行下面的位置

int tot = num*num-1;//终点的位置

trace+=","+p;//记录当前点已经走过

ctop[cnum]+=1;//当前点北方的靶子数值+1

cleft[lnum]+=1;//当前点西面的靶子数值+1

if(isSame(stop,ctop) && isSame(sleft,cleft) && p==num*num-1) {//如果西方、北方靶子数满足输入条件，且到达终点，打印所有路径

System.out.println(trace);

}

if(top>=0 && top<=tot && trace.indexOf(","+top)<0) {//向上走，下一层的数据不能影响当前层，当前层的数据在后续情况中会继续使用，所以要copy当前层数据给下一层

doit1(top, num, stop, sleft, Arrays.copyOfRange(ctop,0,num), Arrays.copyOfRange(cleft,0,num), trace);

}

if(left>=0 && left<=tot && trace.indexOf(","+left)<0) {//向左走

doit1(left, num, stop, sleft, Arrays.copyOfRange(ctop,0,num), Arrays.copyOfRange(cleft,0,num), trace);

}

if(right>=0 && right<=tot && trace.indexOf(","+right)<0) {//向右走

doit1(right, num, stop, sleft, Arrays.copyOfRange(ctop,0,num), Arrays.copyOfRange(cleft,0,num), trace);

}

if(down>=0 && down<=tot && trace.indexOf(","+down)<0) {//向下走

doit1(down, num, stop, sleft, Arrays.copyOfRange(ctop,0,num), Arrays.copyOfRange(cleft,0,num), trace);

}

}

static boolean isSame(int[] a,int[] b){ //判断是否靶子数相同

for(int i=0;i<a.length;i++){

if(a[i]!=b[i])return false;

}

return true;

}

}

测试结果：,0,4,5,1,2,3,7,11,10,9,13,14,15