|
试题 算法训练 跳马
问题描述`
资源限制 时间限制：1.0s 内存限制：256.0MB 问题描述 一个8×8的棋盘上有一个马初始位置为(a,b)，他想跳到(c,d)，问是否可以？如果可以，最少要跳几步？ 输入格式 一行四个数字a,b,c,d。 输出格式 如果跳不到，输出-1；否则输出最少跳到的步数。 样例输入 1 1 2 3 样例输出 1 数据规模和约定 0{1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1,}, {-2, 1},
{-2, -1}}; // 因为马只能走“日”，所以这个二维数组给出所有马能够走的方向，共八方。
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt(), d = sc.nextInt(), len = steps.length;
out.println(getCount(a, b, c, d, len));
}
/**
* @param a 对应题目中的a
* @param b 对应题目中的b
* @param c 对应题目中的c
* @param d 对应题目中的d
* @param len steps数组的长度
* @return 返回最短的次数
*/
public static int getCount(int a, int b, int c, int d, int len) {
list.offer(new int[]{a, b}); // 先将起始位置加进来
int count = 0, innerCount = 0; //count为最后的返回值，innerCount后面会讲
if (list.getFirst()[0] == c && list.getFirst()[1] == d) { // 如果起始位置等于最终的位置，我们直接返回count。
return count;
}
boolean flag = true; // 死循环退出标识
while (flag) {
for (int i = 0; i // 该循环每次都更新马当前位置可走的方向，比方说马当前在(1,1)，完成一次该for循环，马就出现了下一个可以走的位置，存到list里面,
// 如果两层for循环都完成马就会出现8个当前位置可以走的下一个位置，存入list中
at[j] = list.getFirst()[j] + steps[i][j];
}
list.offer(at); // 存入下一个位置到list
innerCount++; // 每一个存入innerCount就会+1，当这里的加1并不能表示次数。因为如果马用的步数为1的时候，innerCount的会是8，而步数用的是2时，innerCount为64
if (at[0] == c && at[1] == d) { // 符号条件，则把退出表示设置为false
flag = false;
break;
}
}
if (Math.pow(8, count + 1) == innerCount) // 基于42行的说法，所以有了当前的判别式。
count++;
list.pollFirst(); // 当当前位置下一步可走的8个方向存入list中，我们删除当前方向，判别下一个方向
}
return count + 1;
}
}
|