Untitled
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(); } }