试题 算法训练 跳马
问题描述`资源限制
时间限制:1.0s 内存限制:256.0MB
问题描述
一个8×8的棋盘上有一个马初始位置为(a,b),他想跳到(c,d),问是否可以?如果可以,最少要跳几步?
输入格式
一行四个数字a,b,c,d。
输出格式
如果跳不到,输出-1;否则输出最少跳到的步数。
样例输入
1 1 2 3
样例输出
1
数据规模和约定
0
注意到,规模非常小,所以可以使用暴力解法解决!
思路这题用广度搜索优先算法(BFS)
具体思路就是,我拿到当前位置(a,b),存入链表中,判别下是否等于目标位置(c,d)。如果是直接返回次数,如果不是,我们将(a,b)可以走的所有下一个位置都加入到链表中,直到找到一个位置等于(c,d)。
下面贴出Java代码
import java.util.*; import static java.lang.System.in; import static java.lang.System.out; public class Main { static Dequelist = new linkedList (); // 这个集合记录每一次走的过程,因为只涉及插入和删除,我用Deque。 static int[][] steps = new int[][]{{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)); } 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 < len; i++) { // 最外层的for循环是控制马走的方向 int[] at = new int[2]; // 临时的at数组装载每一次当前位置的下一个位置 for (int j = 0; j < 2; j++) { // 该循环每次都更新马当前位置可走的方向,比方说马当前在(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; } }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)