# Untitled

unknown
plain_text
17 days ago
1.8 kB
0
Indexable
Never
```2 / 1 / 3 / 1 / 3 / 6 / 3 / 8 / 5 / 7 / 9 / 4 / 11 / 6 / 10 / 10 / 5 / 7 / 5 / 11 / 6 / 22 / 5 / 7 / 9 / 3 / 2 / 7 / 4 / 5 / 9 / 9 / 5 / 7 / 9 / 20 / 5 / 12 / 12 / 8 / 8 / 22 / 11 / 8 / 2 / 10 / 5 / 18 / 49 / 49

public class Solution {
static int[][] m, v;
static int N, M, xx, yy, xxx, yyy;
static boolean check = false;
static int[] dx = { 0, -1, 0, 1 };
static int[] dy = { -1, 0, 1, 0 };
static Queue<Node> q;

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
q = new Queue<>();

for (int tc = 1; tc <= T; tc++) {
N = sc.nextInt();
M = sc.nextInt();
check = false;

m = new int[N + 1][M + 1];
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
m[i][j] = sc.nextInt();
if (m[i][j] == 2) {
xx = i;
yy = j;
}
if (m[i][j] == 3) {
xxx = i;
yyy = j;
}
}
}

int step = 1;
while (!check) {
v = new int[N + 1][M + 1];
bfs(xx, yy, step);
if (check) {
break;
}
step++;
}

System.out.println("Case #" + tc);
System.out.println(step);
}
}

public static boolean isSafe(int x, int y) {
return x > 0 && x <= N && y > 0 && y <= M;
}

public static void bfs(int r, int c, int s) {
q.enQueue(new Node(r, c));
v[r][c] = 1;

Node cr;
while (!q.isEmpty()) {
cr = q.peek();
q.deQueue();

for (int st = 1; st <= s; st++) {
for (int i = 0; i < 4; i++) {
int nx = cr.x + dx[i] * st;
int ny = cr.y + dy[i] * st;
if (isSafe(nx, ny) && v[nx][ny] == 0 && m[nx][ny] != 0) {
q.enQueue(new Node(nx, ny));
v[nx][ny] = 1;
if (v[xxx][yyy] == 1) {
check = true;
return;
}
}
}
if (check)
return;
}
}
}
}```