Untitled
unknown
plain_text
a year ago
1.9 kB
1
Indexable
Never
import java.util.Scanner; public class Solution { static int[][] a = new int[305][305]; static int[][] d = new int[305][305]; static int[][] h = new int[305][305]; static int[] dx = {-1, 1, 0, 0}; static int[] dy = {0, 0, -1, 1}; static int n, m; public static void main(String[] args) { Scanner sc = new Scanner(System.in); //Scanner sc = new Scanner(new File("C:\\Users\\SVMC\\workspace\\adv\\Test\\src\\input.txt")); int T = sc.nextInt(); for(int t=1; t<=T; t++) { m=sc.nextInt(); n=sc.nextInt(); int y1=sc.nextInt()-1, x1=sc.nextInt()-1; int y2=sc.nextInt()-1, x2=sc.nextInt()-1; for(int i=0; i<n; i++) { String s = sc.next(); for(int j=0; j<s.length(); j++) { a[i][j] = s.charAt(j)-'0'; } } for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { d[i][j] = 100000007; h[i][j] = -1; } } BFS(x1, y1); if(d[x2][y2]!=100000007) { System.out.println(d[x2][y2]-1); }else { System.out.println(-1); } } } static void BFS(int x, int y) { d[x][y] = 0; int[] qx = new int[305*305]; int[] qy = new int[305*305]; int l=0, r=0; qx[r]=x; qy[r++]=y; while(l<r) { x = qx[l]; y=qy[l++]; for(int i=0; i<4; i++) { int xx = x+dx[i]; int yy = y+dy[i]; if(xx>=0 && xx<n && yy>=0 && yy<m) { int tt = a[xx][yy]; // System.out.println(tt); } if(xx>=0 && xx<n && yy>=0 && yy<m && a[xx][yy]==0) { int tmp = d[x][y]; if(i!=h[x][y]) { tmp+=1; } if(tmp<d[xx][yy]) { d[xx][yy]=tmp; h[xx][yy]=i; // System.out.println(xx+" "+yy +" "+ tmp + " "+h[xx][yy]); qx[r]=xx; qy[r++]=yy; }else if(tmp==d[xx][yy] && h[xx][yy]!=i){ h[xx][yy]=i; qx[r]=xx; qy[r++]=yy; } } } } } }