Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.1 kB
8
Indexable
Never
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class FassRobot {
	static int n, m;
	static int a[][];
	static int dx[] = { 0, 0, 1, -1 };
	static int dy[] = { 1, -1, 0, 0 };
	static int Qx[];
	static int Qy[];
	static int visit[][];

	static int startX, startY, endX, endY;

	public static void main(String[] args) {
		try {
			System.setIn(new FileInputStream("fastRobot"));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
		Scanner sc = new Scanner(System.in);
		int numTest = sc.nextInt();
		for (int tc = 1; tc <= numTest; tc++) {
			n = sc.nextInt();
			m = sc.nextInt();
			startY = sc.nextInt();
			startX = sc.nextInt();
			endY = sc.nextInt();
			endX = sc.nextInt();
			a = new int[m + 2][n + 2];
			sc.nextLine();
			String line;
			visit = new int[1000][1000];
			for (int i = 0; i < m; i++) {
				line = sc.nextLine();
				for (int j = 0; j < n; j++) {
					a[i][j] = line.charAt(j) - '0';
					visit[i][j] = -1;
				}
			}
			Qx = new int[10000000];
			Qy = new int[10000000];
			BFS(startX-1, startY-1);// mang bat dau tu 0
			System.out.println("Case#"+tc+" "+visit[endX-1][endY-1]);
			
//			for (int k = 0; k < m; k++) {
//				for (int l = 0; l < n; l++) {
//					System.out.print(visit[k][l] + " ");
//				}
//				System.out.println();
//			}
//			System.out.println();
		}
	}

	public static void BFS(int x, int y) {
		int front = 0;
		int rear = 0;

		Qx[rear] = x;
		Qy[rear] = y;
		rear++;
//		visit[x][y] = 0;
		while (front != rear) {
			int tmpx = Qx[front];
			int tmpy = Qy[front];
			front++;
			for (int i = 0; i < 4; i++) {
				int xx = tmpx + dx[i];
				int yy = tmpy + dy[i];

				while (xx >= 0 && xx < m && yy >= 0 && yy < n
						&& visit[xx][yy] == -1 && a[xx][yy] == 0) {
					
					visit[xx][yy] = visit[tmpx][tmpy] + 1;
					if (xx == endX && yy == endY) {
						return;
					}
					Qx[rear] = xx;
					Qy[rear] = yy;
					rear++;

					xx = xx + dx[i];
					yy = yy + dy[i];

				}
			}
			
		}

	}

}