Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.0 kB
3
Indexable
Never
package Fast_robot;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {
	static int n, m, res, xs, ys, xe, ye, count;
	static int[][] a, visit, lan;
	static int[] dx = { 0, 1, 0, -1 }, dy = { 1, 0, -1, 0 };

	public static void BFS() {
		int front = 0, rear = 0;
		int[] queueX = new int[9000005], queueY = new int[9000005];
		queueX[front] = xs;
		queueY[front] = ys;
		lan[xs][ys] = 0;
		visit[xs][ys] = 1;
		while (front <= rear) {
			int x = queueX[front], y = queueY[front];
			int c = lan[x][y];
			for (int i = 0; i < 4; i++) {
				int newx = x + dx[i], newy = y + dy[i];
//				if (newx >= 0 && newy >= 0 && newx < n && newy < m
//						&& visit[newx][newy] == 0 && a[newx][newy] != 1) {
					while (newx >= 0 && newy >= 0 && newx < n && newy < m
							&& visit[newx][newy] == 0 && a[newx][newy] != 1) {
						
						rear++;
						queueX[rear] = newx;
						queueY[rear] = newy;
						visit[newx][newy] = 1;
						lan[newx][newy] = c + 1;
						newx = newx + dx[i]; newy = newy + dy[i];
					}

//				}
			}
			front++;
		}

	}
	

	public static void main(String[] args) {
		try {
			System.setIn(new FileInputStream("input.txt"));
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		Scanner scanner = new Scanner(System.in);
		int test = scanner.nextInt();
		for (int t = 1; t <= test; t++) {
			m = scanner.nextInt();
			n = scanner.nextInt();
			a = new int[n][m];
			visit = new int[n][m];
			lan = new int[n][m];
			count = 0;
			ys = scanner.nextInt() - 1;
			xs = scanner.nextInt() - 1;
			ye = scanner.nextInt() - 1;
			xe = scanner.nextInt() - 1;
			for (int i = 0; i < n; i++) {
				String s = scanner.next();
				for (int j = 0; j < m; j++) {
					a[i][j] = s.charAt(j) - '0';
				}
			}
			res = 10000000;
			
			
			BFS();
			
			
			System.out.println(lan[xe][ye]-1);
		}
		scanner.close();
	}
}