本题是一道BFS题目
只需要将2个机器人的坐标一起作为状态,比如4元组(xA, yA, xB, yB),进行BFS即可。
初始状态(1, 1, N, M),目标状态(N, M, 1, 1)。
本题是一道BFS题目
只需要将2个机器人的坐标一起作为状态,比如4元组(xA, yA, xB, yB),进行BFS即可。
初始状态(1, 1, N, M),目标状态(N, M, 1, 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;
}
}
}
点错了,麻烦删除一下评论@admin?