P1443 马的遍历

题目描述:

有一个 𝑛×𝑚n×m 的棋盘，在某个点 (𝑥,𝑦)(x,y) 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。

代码:

package lanqiao;import java.util.*;public class Main {static int n,m,x,y;static int[][] a = new int[410][410];static int[] aa = new int[] {2, 1, 2, -1, -2, -1, -2, 1};static int[] bb = new int[] {1, 2, -1, -2, -1, 2, 1, -2};public static void main(String[] args) {Scanner sc = new Scanner(System.in);n = sc.nextInt();m = sc.nextInt();x = sc.nextInt();y = sc.nextInt();//初始化数组for(int i = 1;i <= n;i ++){for(int j = 1;j <= m;j ++){a[i][j] = -1;}}dfs(x,y,0);a[x][y] = 0;for(int i = 1;i <= n;i ++){for(int j = 1;j <= m;j ++){System.out.printf("%-5d", a[i][j]);}System.out.println();}}public static void dfs(int x,int y,int t){if(t >200) //DFS不加剪枝的话需要加阙值{return;}a[x][y] = t;for(int i = 0;i < 8;i ++){if(x + aa[i] >= 1 && y + bb[i] >= 1 && x + aa[i] <= n && y + bb[i] <= m&& (a[x + aa[i]][y + bb[i]] == -1 || a[x + aa[i]][y + bb[i]] > t + 1))//需要对未走过的格子,或者新路线步数较短的格子进行重新赋值{dfs(x + aa[i],y + bb[i],t + 1);}}}
}