# Untitled

unknown
plain_text
a month ago
4.8 kB
1
Indexable
Never
```package hugo;

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

public class Solution {
static int n, m, sr, sc, lua, ho, lt, res;
static int[][] kc, fire, visit, f, r, out;
static int[] qx = new int[1005], qy = new int[1005], outx, outy;
static int[] dx = { 0, 1, 0, -1 }, dy = { 1, 0, -1, 0 };
static boolean checkout;

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

// lan lua -1 lua -2 ho
public static void lanLua() {
visit = new int[n][m];
int front = 0, rear = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (fire[i][j] == -1) {
qx[rear] = i;
qy[rear] = j;
visit[i][j] = 1;
f[i][j] = 0;
rear++;
}
if (fire[i][j] == -2) {
f[i][j] = -2;
}
}
}
while (front < rear) {
int x = qx[front], y = qy[front];
int c = f[x][y];
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (checkout(nx, ny) && fire[nx][ny] != -2) {
if (visit[nx][ny] == 0) {
qx[rear] = nx;
qy[rear] = ny;
f[nx][ny] = c + 1;
visit[nx][ny] = 1;
rear++;
} else if (visit[nx][ny] == 1) {
if (f[nx][ny] > c + 1) {
qx[rear] = nx;
qy[rear] = ny;
f[nx][ny] = c + 1;
rear++;
}
}
}
}

front++;
}
}

public static void updateLua(){
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(f[i][j] == 0 && fire[i][j] == 0){
f[i][j] = Integer.MAX_VALUE;
}
}
}
}

public static void backTrack(int x, int y, int time, int count){
//		System.out.println(x + " - " + y + " " + time + " " + count);
for (int i = 0; i < lt; i++) {
if (x == outx[i] && y == outy[i]) {
res = Math.max(res, count);
checkout = true;
break;
}
}
for (int i = 0; i < 4; i++) {
// System.out.println("for");
int nx = x + dx[i], ny = y + dy[i];
if (checkout(nx, ny) && visit[nx][ny] == 0 && fire[nx][ny] != -1) {
if(fire[nx][ny] == 0 && time+1 < f[nx][ny]){
visit[nx][ny] = 1;
backTrack(nx, ny, time+1, count + kc[nx][ny]);
visit[nx][ny] = 0;
}else if(fire[nx][ny] == -2){
visit[nx][ny] = 1;
backTrack(nx, ny, time+2, count + kc[nx][ny]);
visit[nx][ny] = 0;
}
}
}

}

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();
sr = scanner.nextInt() - 1;
sc = scanner.nextInt() - 1;
fire = new int[n][m];
f = new int[n][m];
r = new int[n][m];
kc = new int[n][m];
out = new int[n][m];
lua = scanner.nextInt();
for (int i = 0; i < lua; i++) {
fire[scanner.nextInt() - 1][scanner.nextInt() - 1] = -1;
}
ho = scanner.nextInt();
for (int i = 0; i < ho; i++) {
fire[scanner.nextInt() - 1][scanner.nextInt() - 1] = -2;
}
lt = scanner.nextInt();
outx = new int[lt];
outy = new int[lt];
for (int i = 0; i < lt; i++) {
outx[i] = scanner.nextInt() - 1;
outy[i] = scanner.nextInt() - 1;
out[outx[i]][outy[i]] = 1;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
kc[i][j] = scanner.nextInt();
}
}

//			for (int i = 0; i < n; i++) {
//				for (int j = 0; j < m; j++) {
//					System.out.print(fire[i][j] + " ");
//				}
//				System.out.println();
//			}
//			System.out.println();

lanLua();
updateLua();
//			for (int i = 0; i < n; i++) {
//				for (int j = 0; j < m; j++) {
//					System.out.print(f[i][j] + " ");
//				}
//				System.out.println();
//			}
//			System.out.println();
//
//			for (int i = 0; i < n; i++) {
//				for (int j = 0; j < m; j++) {
//					System.out.print(kc[i][j] + " ");
//				}
//				System.out.println();
//			}
//			System.out.println();

out[sr][sc] = 2;
//			System.out.println();
//			for (int i = 0; i < n; i++) {
//				for (int j = 0; j < m; j++) {
//					System.out.print(out[i][j] + " ");
//				}
//				System.out.println();
//			}
//			System.out.println();

res = 0; checkout = false;
visit = new int[n][m];
visit[sr][sc] = 1;
backTrack(sr, sc, 0, kc[sr][sc]);

//			System.out.println(n + " " + m);
if(checkout){
System.out.println("Case #" + t + "\n" + res);
}else{
System.out.println("Case #" + t + "\n-1");
}

}
scanner.close();
}
}
```