Untitled
unknown
plain_text
5 months ago
6.4 kB
2
Indexable
Never
package _1906; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class Hugoold { static int N, M, SR, SC, K, H, numExit, ans, sum; static int a[][], b[][];// b luu gia tri truoc khi lua chay static int fire[][], lake[][], Exit[][], visitDiChuyen[][]; static boolean isChay[][]; static int dx[] = { 0, 0, 1, -1 }; static int dy[] = { 1, -1, 0, 0 }; static int Qx[]; static int Qy[]; static int visit[][], visitNhomLua[]; static int d[][]; public static void main(String[] args) { try { System.setIn(new FileInputStream("Hugo")); } catch (FileNotFoundException e) { e.printStackTrace(); } Scanner sc = new Scanner(System.in); int numTest = sc.nextInt(); for (int tc = 1; tc <= numTest; tc++) { N = sc.nextInt(); M = sc.nextInt(); SR = sc.nextInt(); SC = sc.nextInt(); K = sc.nextInt(); fire = new int[2][K]; for (int i = 0; i < K; i++) { fire[0][i] = sc.nextInt(); fire[1][i] = sc.nextInt(); } H = sc.nextInt(); lake = new int[2][H]; for (int i = 0; i < H; i++) { lake[0][i] = sc.nextInt(); lake[1][i] = sc.nextInt(); } numExit = sc.nextInt(); Exit = new int[2][numExit]; for (int i = 0; i < numExit; i++) { Exit[0][i] = sc.nextInt(); Exit[1][i] = sc.nextInt(); } a = new int[N][M]; b = new int[N][M]; visitDiChuyen = new int[N][M]; isChay = new boolean[N][M]; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { a[i][j] = sc.nextInt(); } } cbiDuLieu(); for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { b[i][j] = a[i][j]; } } // ans = 0; // backTrack(SR - 1, SC - 1, 0); // index mang // System.out.println("Case #" + tc); // System.out.println(ans); isfire(); for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { System.out.print(isChay[i][j] + " "); } System.out.println(); } System.out.println(); System.out.println("mang trung gian b"); for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { System.out.print(b[i][j] + " "); } System.out.println(); } System.out.println(); System.out.println("mang a"); for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { System.out.print(a[i][j] + " "); } System.out.println(); } // unfire(); System.out.println(); System.out.println("unfire"); for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { System.out.print(isChay[i][j] + " "); } System.out.println(); } for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { System.out.print(a[i][j] + " "); } System.out.println(); } System.out.println(); } } public static void cbiDuLieu() { for (int k = 0; k < K; k++) { int x = fire[0][k] - 1;// index mang tu 0 int y = fire[1][k] - 1; a[x][y] = 10000; // fire } for (int k = 0; k < H; k++) { int x = lake[0][k] - 1;// index mang tu 0 int y = lake[1][k] - 1; a[x][y] += 3000; // lake } } public static void thoiGianChay() { for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { } } } public static int BFS(int x, int y, int luaX, int luaY) { Qx = new int[N*M]; Qy = new int[N*M]; visit = new int[N+2][M+2]; d = new int[N + 2][M + 2]; int front = 0; int rear = 0; Qx[rear] = x; Qy[rear] = y; rear++; visit[x][y] = 1; while (front != rear) { int tmpx = Qx[front]; int tmpy = Qy[front]; front++; for (int i = 0; i < 4; i++) { int xx = tmpx + dx[i]; int yy = tmpy + dy[i]; if (inMatrix(xx, yy)&&visit[xx][yy] == 0) { if (a[xx][yy] <3000) { d[xx][yy] = d[tmpx][tmpy] + 1; visit[xx][yy] = 1; Qx[rear] = xx; Qy[rear] = yy; rear++; } // if (xx == vetBanxX && yy == vetBanxY) { // d[xx][yy] = d[tmpx][tmpy] + 1; // return d[xx][yy]; // } } } } public static boolean inMatrix(int x, int y) { if (x >= 0 && x < N && y >= 0 && y < M) return true; return false; } public static void isfire() { for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (a[i][j] == 10000) { // ||isChay[i][j] == true isChay[i][j] = true; for (int k = 0; k < 4; k++) { int xx = i + dx[k]; int yy = j + dy[k]; if (inMatrix(xx, yy) && !isChay[xx][yy] && a[xx][yy] < 3000) { visitDiChuyen[xx][yy] = 1; b[xx][yy] = a[xx][yy]; // a[xx][yy]=10000; isChay[xx][yy] = true; } } } } } // update nhung o bi lan lua for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (isChay[i][j] == true) { // b[i][j] = 10000; a[i][j] = 10000; } } } } public static void unfire() { for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { for (int k = 0; k < 4; k++) { int xx = i + dx[k]; int yy = j + dy[k]; if (inMatrix(xx, yy)) { visitDiChuyen[xx][yy] = 0; isChay[xx][yy] = false; } } } } for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (!isChay[i][j]) a[i][j] = b[i][j]; } } } public static int soGio(int x, int y) { if (a[x][y] >= 3000 && a[x][y] <= 4000)// lake return 2; if (a[x][y] < 3000) { return 1; } return 0; } public static boolean isSafe(int x, int y) { if (a[x][y] <= 4000) return true; return false; } public static void backTrack(int SR, int SC, int sum) { for (int i = 0; i < numExit; i++) { if (SR == Exit[0][i] - 1 && SC == Exit[1][i] - 1) { ans = Math.max(ans, sum); return; } } for (int k = 0; k < 4; k++) { int tmpx = SR + dx[k]; int tmpy = SC + dy[k]; if (inMatrix(tmpx, tmpy) && isSafe(tmpx, tmpy) && visitDiChuyen[tmpx][tmpy] == 0) { if (soGio(tmpx, tmpy) == 2) { isfire(); isfire(); backTrack(tmpx, tmpy, sum + a[tmpx][tmpy] % 3000); unfire(); unfire(); } if (soGio(tmpx, tmpy) == 1) { isfire(); backTrack(tmpx, tmpy, sum + a[tmpx][tmpy]); unfire(); } } } } }