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