[数据结构与算法]洛谷——马的遍历

题目链接：马的遍历

java代码：

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

	public static int n,m,r,c;
//	用两个数组记录马可以走的8个方向
	public static int dx[] = {-1,-2,-2,-1,1,2,2,1},dy[] = {2,1,-1,-2,2,1,-1,-2};
//	记录最后输出结果
	public static int a[][] = new int[410][410];
//	BFS需要借助队列存放坐标
	public static Queue<Integer> q = new LinkedList<>();
	public static Scanner in = new Scanner(System.in);
	
    public static void main(String[] args) {
       
    	n = in.nextInt(); m = in.nextInt();
    	r = in.nextInt(); c = in.nextInt();
    	
    	for(int i=0;i<410;++i) Arrays.fill(a[i], -1);
    	
    	bfs();
    	
    	for(int i=1;i<=n;++i) {
    		for(int j=1;j<=m;++j) {
//    			场宽为5，左对齐。。。
    			System.out.printf("%-5d",a[i][j]);
    		}
    		System.out.println();
    	}
    }
    
    public static void bfs() {
//    	起点坐标入队
    	q.add(r);
    	q.add(c);
    	a[r][c] = 0;
    	while(q.isEmpty()==false) {
//    		坐标出队
    		int row = q.poll(), col = q.poll();
    		
    		for(int i=0;i<8;++i) {
    			int x = row+dx[i], y = col+dy[i];
//    			这里判断坐标是否出界以及是否走过了
    			if(x>=1&&x<=n&&y>=1&&y<=m&&a[x][y]==-1) {
    				q.add(x);
        			q.add(y);
//        			这里用全局变量来更新a数组的话不好处理，所以需要借助上一个坐标的记录的步数
        			a[x][y] = a[row][col]+1;
    			}
    		}
    		
    	}
    }
      
}