hiho一下第320周《两个机器人》题目分析

3
1

本题是一道BFS题目

只需要将2个机器人的坐标一起作为状态,比如4元组(xA, yA, xB, yB),进行BFS即可。

初始状态(1, 1, N, M),目标状态(N, M, 1, 1)。

1 answer(s)

1

import java.util.LinkedList; import java.util.Scanner;

public class Main{ static int[][] map; public static void main(String[] args) { Scanner sc = new Scanner(System.in); String first = sc.nextLine(); String arr[] = first.split(" "); int n = Integer.valueOf(arr[0]); int m = Integer.valueOf(arr[1]); int re=Integer.MAX_VALUE; map = new int[n][m]; for(int j=0;j list = new LinkedList(); list.push(node); while(!list.isEmpty()){ Node tmp = list.pop(); int r = tmp.re; if(tmp.xa==n-1 && tmp.ya==m-1 && tmp.xb==0 && tmp.yb==0){ if(r=n || map[tmp.xa+1][tmp.ya]=='1'){ x=true; }if(tmp.xb-1<0 || map[tmp.xb-1][tmp.yb]=='1'){ y=true; } if(!x && !y){ Node n1 = new Node(tmp.xa+1, tmp.ya, tmp.xb-1, tmp.yb,r); list.push(n1); } if(!x && y) { Node n1 = new Node(tmp.xa+1, tmp.ya, tmp.xb, tmp.yb,r); list.push(n1); } if(x && !y) { Node n1 = new Node(tmp.xa, tmp.ya, tmp.xb-1, tmp.yb,r); list.push(n1); }

        }
        if(tmp.xa!=tmp.xb || (tmp.xa==tmp.xb && tmp.ya+1!=tmp.yb-1 && tmp.ya+1!=tmp.yb)) {
            boolean x=false,y=false;
            if(tmp.ya+1>=m || map[tmp.xa][tmp.ya+1]=='1'){
                x=true;
            }if(tmp.yb-1<0 || map[tmp.xb][tmp.yb-1]=='1'){
                y=true;
            }
            if(!x && !y){
                Node n2 = new Node(tmp.xa, tmp.ya+1, tmp.xb, tmp.yb-1,r);
                list.push(n2);
            }
            if(!x && y) {
                Node n2 = new Node(tmp.xa, tmp.ya+1, tmp.xb, tmp.yb,r);
                list.push(n2);
            }
            if(x && !y) {
                Node n2 = new Node(tmp.xa, tmp.ya, tmp.xb, tmp.yb-1,r);
                list.push(n2);
            }

        }
    }
    if(re==Integer.MAX_VALUE){
        System.out.println(-1);
    }else {
        System.out.println(re);
    }
}
private static class Node{
    int xa,ya,xb,yb,re;
    public Node(int xa, int ya, int xb, int yb) {
        this(xa,ya,xb,yb,0);
    }
    public Node(int xa, int ya, int xb, int yb,int re) {
        this.xa = xa;
        this.ya = ya;
        this.xb = xb;
        this.yb = yb;
        this.re = re;
    }
}

}

write answer 切换为英文 切换为中文


转发分享