Untitled

 avatar
unknown
plain_text
a year ago
1.7 kB
3
Indexable
public class Solution {
	static int N, M, P, cnt;
	static int[][] v, m, nm;
	static int[][] t = { 
			{ 0, 0, 0, 0 }, 
			{ 1, 1, 1, 1 }, 
			{ 1, 0, 1, 0 }, 
			{ 0, 1, 0, 1 }, 
			{ 1, 1, 0, 0 }, 
			{ 0, 1, 1, 0 },
			{ 0, 0, 1, 1 }, 
			{ 1, 0, 0, 1 } };

	static int[] dx = { -1, 0, 1, 0 };
	static int[] dy = { 0, 1, 0, -1 };
	static Queue<Node> q;

	public static void main(String[] args) throws Exception {
		int T = sc.nextInt();
		q = new Queue();
		for (int tc = 1; tc <= T; tc++) {
			cnt = 1;
			N = sc.nextInt();
			M = sc.nextInt();
			int xt = sc.nextInt();
			int yt = sc.nextInt();
			P = sc.nextInt();
			v = new int[N][M];
			nm = new int[N][M];
			m = new int[N][M];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					m[i][j] = sc.nextInt();
				}
			}
			BFS(xt, yt);
			System.out.println("Case #" + tc);
			System.out.println(cnt);
		}
	}

	static void BFS(int xt, int yt) throws Exception {
		q.reset();
		q.enQueue(new Node(xt, yt));
		v[xt][yt] = 1;
		nm[xt][yt] = 1;
		Node no;
		while (!q.isEmpty()) {
			no = q.peek();
			q.deQueue();

			for (int i = 0; i < 4; i++) {
				int nx = no.x + dx[i];
				int ny = no.y + dy[i];
				if (check(nx, ny)) {
					if (m[nx][ny] != 0 && v[nx][ny] == 0 
                            && t[m[no.x][no.y]][i] == 1
							&& t[m[nx][ny]][(i + 2) % 4] == 1) {
						nm[nx][ny] = nm[no.x][no.y] + 1;
						if (nm[nx][ny] > P)
							return;
						cnt++;
						q.enQueue(new Node(nx, ny));
						v[nx][ny] = 1;
					}
				}
			}
		}
	}

	static boolean check(int x, int y) {
		return x >= 0 && x < N && y >= 0 && y < M;
	}
Editor is loading...
Leave a Comment