Untitled
unknown
plain_text
10 months ago
2.2 kB
2
Indexable
Never
package Practice; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class Mario_Climb { static int n, m, arr[][], visit[][], front, rear, x, y; static Position dat[] = new Position[1000005]; static void reset() { front = rear; } static void push(Position val) { dat[++front] = val; } static Position pop() { return dat[++rear]; } static boolean isE() { return front == rear; } static void resetV() { for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { visit[i][j] = 0; } } } static int bfs(int k) { reset(); resetV(); Position position = new Position(x, y); push(position); visit[x][y] = 1; int spinx[] = new int[k * 4]; int spiny[] = new int[k * 4]; spinx[0] = spinx[1] = 0; spiny[0] = 1; spiny[1] = -1; int count = 2; int num = 1; for (int i = 0; i < k; i++) { spinx[count] = num; spinx[count + 1] = -num; count += 2; num++; } while (!isE()) { position = pop(); int cr = position.x; int cc = position.y; for (int i = 0; i < count; i++) { int nr = cr + spinx[i]; int nc = cc + spiny[i]; if (nr >= 0 && nr < n && nc >= 0 && nc < m && arr[nr][nc] != 0 && visit[nr][nc] == 0) { position = new Position(nr, nc); push(position); visit[nr][nc] = 1; if (arr[nr][nc] == 3) { return k; } } } } return -1; } public static void main(String[] args) throws FileNotFoundException { System.setIn(new FileInputStream("Text")); Scanner scanner = new Scanner(System.in); int tc = scanner.nextInt(); for (int Case = 1; Case <= tc; Case++) { n = scanner.nextInt(); m = scanner.nextInt(); arr = new int[n][m]; visit = new int[n][m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { arr[i][j] = scanner.nextInt(); if (arr[i][j] == 2) { x = i; y = j; } } } int ans = 0; for (int i = 1; i < n; i++) { if (bfs(i) != -1) { ans = i; break; } } System.out.println("Case #" + Case); System.out.println(ans); } } }
Leave a Comment