题解 P1443 【马的遍历】

bestMatch · 2020-01-31 18:08:55 · 题解

java BFS

import java.io.*;
import java.util.*;
public class Main{
    int x,y;
    public Main(int x,int y) {
        this.x=x;
        this.y=y;
    }
    static int n,m,a,b,N=410;
    static int[][] g=new int[N][N];
    static boolean[][] st=new boolean[N][N];
    static int[] dx= {2,-2,2,-2,-1,1,-1,1},dy={1,1,-1,-1,2,2,-2,-2};
    static public void main(String[] args) throws IOException{
        BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
        String[] num=in.readLine().split(" ");
        n=Integer.parseInt(num[0]);
        m=Integer.parseInt(num[1]);
        a=Integer.parseInt(num[2]);
        b=Integer.parseInt(num[3]);
        bfs();
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=m;j++)
            {
                if(st[i][j])
                    System.out.format("%-5d",g[i][j]);
                else
                    System.out.format("%-5d",-1);
            }
            System.out.println();
        }
        in.close();
       }
    static public void bfs() {
        Queue<Main> q=new LinkedList<>();
        q.add(new Main(a,b));
        st[a][b]=true;
        while(!q.isEmpty()) {
            Main t=q.peek();
            q.poll();
            for(int i=0;i<8;i++) {
                int x=t.x+dx[i];
                int y=t.y+dy[i];
                if(x>0 && x<=n && y>0 && y<=m && !st[x][y]) {
                    g[x][y]=g[t.x][t.y]+1;
                    st[x][y]=true;
                    q.add(new Main(x,y));
                }
            }

        }
    }
}