Untitled

 avatar
unknown
plain_text
2 years ago
6.4 kB
3
Indexable
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();
				}
			}
		}

	}
}