Untitled

mail@pastecode.io avatarunknown
plain_text
a month ago
4.1 kB
1
Indexable
Never
package hugo_ban_dau;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {
	static int n, m, res, xs, ys, h;
	static int[][] a, visit, value;
	static int[][] dx = { { -1, 0, 1, 0 }, { -1, 1 }, { 0, 0 }, { -1, 0 }, { 1, 0 }, { 0, 1 }, { 0, -1 } };
	static int[][] dy = { { 0, -1, 0, 1 }, { 0, 0 }, { -1, 1 }, { 0, 1 }, { 0, 1 }, { -1, 0 }, { -1, 0 } };
	static int[] qx = new int[10000], qy = new int[10000], dientich, ke,
			quex = new int[10000], quey = new int[10000];

	public static boolean checkOut(int x, int y) {
		if (x < 0 || x >= n || y < 0 || y >= m) {
			return false;
		}
		return true;
	}

	public static boolean find(int v, int x, int i) {
		if (v == 1 && (x == 1 || x == 2 || x == 5 || x == 6) && i == 0)
			return true;
		if (v == 1 && (x == 1 || x == 3 || x == 4 || x == 5) && i == 1)
			return true;
		if (v == 1 && (x == 1 || x == 2 || x == 4 || x == 7) && i == 2)
			return true;
		if (v == 1 && (x == 1 || x == 3 || x == 6 || x == 7) && i == 3)
			return true;
		if (v == 2 && (x == 1 || x == 2 || x == 5 || x == 6) && i == 0)
			return true;
		if (v == 2 && (x == 1 || x == 2 || x == 4 || x == 7) && i == 1)
			return true;
		if (v == 3 && (x == 1 || x == 3 || x == 4 || x == 5) && i == 0)
			return true;
		if (v == 3 && (x == 1 || x == 3 || x == 6 || x == 7) && i == 1)
			return true;
		if (v == 4 && (x == 1 || x == 2 || x == 5 || x == 6) && i == 0)
			return true;
		if (v == 4 && (x == 1 || x == 3 || x == 6 || x == 7) && i == 1)
			return true;
		if (v == 5 && (x == 1 || x == 2 || x == 4 || x == 7) && i == 0)
			return true;
		if (v == 5 && (x == 1 || x == 3 || x == 6 || x == 7) && i == 1)
			return true;
		if (v == 6 && (x == 1 || x == 3 || x == 4 || x == 5) && i == 0)
			return true;
		if (v == 6 && (x == 1 || x == 2 || x == 4 || x == 7) && i == 1)
			return true;
		if (v == 7 && (x == 1 || x == 3 || x == 4 || x == 5) && i == 0)
			return true;
		if (v == 7 && (x == 1 || x == 2 || x == 5 || x == 6) && i == 1)
			return true;
		return false;
	}

	public static void BFS(int xs, int ys, int h){
		int front = 0, rear = 0;
		qx[front] = xs;
		qy[front] = ys;
		visit[xs][ys] = 1;
		value[xs][ys] = 1;
		while(front <= rear){
			int xt = qx[front], yt = qy[front];
			int val = value[xt][yt];
			int v = a[xt][yt];
//			System.out.println(xs +" " + ys + " " + v);
			if(v == 1){
				for(int i = 0; i < 4; i++){
					int nx = xt + dx[v-1][i], ny = yt + dy[v-1][i];
					if(checkOut(nx, ny) && visit[nx][ny] == 0 && a[nx][ny] != 0 && find(v, a[nx][ny], i) ){
						rear++;
						qx[rear] = nx;
						qy[rear] = ny;
						visit[nx][ny] = 1;
						value[nx][ny] = val+1;
					}
				}
			}else{
				for(int i = 0; i < 2; i++){
					int nx = xt + dx[v-1][i], ny = yt + dy[v-1][i];
					if(checkOut(nx, ny) && visit[nx][ny] == 0 && a[nx][ny] != 0 && find(v, a[nx][ny], i)){
						rear++;
						qx[rear] = nx;
						qy[rear] = ny;
						visit[nx][ny] = 1;
						value[nx][ny] = val+1;
					}
				}
			}
			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++) {
			n = scanner.nextInt();
			m = scanner.nextInt();
			a = new int[n][m];
			visit = new int[n][m];
			value = new int[n][m];
			xs = scanner.nextInt();
			ys = scanner.nextInt();
			h = scanner.nextInt();
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					a[i][j] = scanner.nextInt();
				}
			}

			res = 0;
			BFS(xs, ys, h);

			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					if (value[i][j] <= h && value[i][j] != 0) {
						res++;
					}
//					System.out.print(value[i][j] + " ");
				}
//				System.out.println();
			}

			System.out.println("Case #" + t + "\n" + res);

		}
		scanner.close();
	}

}