P2658 汽车拉力比赛 JAVA题解

package 篮桥杯.d;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    //自定义的输入类，比普通Scanner快两倍多
    static class Scanner{
        StreamTokenizer streamTokenizer=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        public int nextInt() throws IOException {
            streamTokenizer.nextToken();
            return (int) streamTokenizer.nval;
        }
    }
    //自定义在广度优先搜索中纪录位置的类
    static class Pair{
        int x;
        int y;
        Pair(int a,int b){
            x=a;
            y=b;
        }
    }
    static int n,m,bytex,bytey,count;//bytex,bytey是纪录广度优先搜索中开始搜索的位置 count是记录路标的个数
    static int[][] arr,div={{-1,0},{1,0},{0,1},{0,-1}};//arr是高度div是方位
    static byte[][] bytes;//纪录路标的位置
    static boolean[][] span;//纪录走过的位置
    static Queue<Pair> queue=new LinkedList<>();//广搜所使用的队列
    public static void main(String[] args) throws IOException {
        Scanner sc=new Scanner();
        n=sc.nextInt();
        m=sc.nextInt();
        arr=new int[n+1][m+1];
        bytes=new byte[n+1][m+1];
        span=new boolean[n+1][m+1];
        for (int i = 1; i <=n ; i++) {//输入高度
            for (int j = 1; j <=m ; j++) {
                arr[i][j]=sc.nextInt();
            }
        }
        for (int i = 1; i <=n ; i++) {//输入路标
            for (int j = 1; j <=m ; j++) {
                bytes[i][j]= (byte) sc.nextInt();
                if (bytes[i][j]==1){//纪录路标位置，虽然会覆盖但只要是路标从哪搜都可以
                    bytex=i;
                    bytey=j;
                    count++;//纪录路标个数
                }
            }
        }
        //用二分的模板可以从b站上搜到
        int l=-1,r=1000000010;
        while (l+1!=r){
            int m=l+r>>>1;
            if (bsf(m)){
                r=m;
            }else {
                l=m;
            }
        }
        System.out.println(r);
    }

    private static boolean bsf(int k) {
        int c=1;
        queue.clear();
        span=new boolean[n+1][m+1];
        queue.add(new Pair(bytex,bytey));
        span[bytex][bytey]=true;
        while (!queue.isEmpty()){
            Pair poll = queue.poll();
            for (int i = 0; i < div.length; i++) {
                int xx=poll.x+div[i][0];
                int yy=poll.y+div[i][1];
                if (xx>=1&&xx<=n&&yy>=1&&yy<=m&&!span[xx][yy]&&Math.abs(arr[poll.x][poll.y]-arr[xx][yy])<=k){
                    if (bytes[xx][yy]==1){
                        c++;
                        if (c==count){
                            return true;
                        }
                    }
                    span[xx][yy]=true;
                    queue.add(new Pair(xx,yy));
                }
            }
        }
        return false;
    }
}