Untitled

mail@pastecode.io avatar
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;
					}
				}
			}
		}
	}
}