Untitled

#include <stdio.h>

#define MAX_SIZE 20
#define MAX_INT 1000000000

int dx[] = {0, -1, 0, 1};
int dy[] = {-1, 0, 1, 0};
int diamond[MAX_SIZE][MAX_SIZE];
bool exit[MAX_SIZE][MAX_SIZE];
bool lake[MAX_SIZE][MAX_SIZE];
int fire[MAX_SIZE][MAX_SIZE];
bool visited[MAX_SIZE][MAX_SIZE];
int Q[MAX_SIZE * MAX_SIZE];
int front, rear;
int N, M, maxDiamond;

void spreadFire()
{
	int r, c, nextR, nextC;
	while (front <= rear) {
		r = Q[front] / MAX_SIZE;
		c = Q[front++] % MAX_SIZE;
		for (int d = 0; d < 4; d++) {
			nextR = r + dy[d];
			nextC = c + dx[d];
			if (nextR < 1 || nextR > N || nextC < 1 || nextC > M)
				continue;
			if (fire[nextR][nextC] > fire[r][c] + 1 && !lake[nextR][nextC]) {
				fire[nextR][nextC] = fire[r][c] + 1;
				Q[++rear] = nextR * MAX_SIZE + nextC;
			}
		}
	}
}

void go(int r, int c, int time, int collected)
{
	if (exit[r][c]) {//exit
		if (collected > maxDiamond)
			maxDiamond = collected;
	}

	for (int d = 0; d < 4; d++) {
			int nextR = r + dy[d];
			int nextC = c + dx[d];
			if (nextR < 1 || nextR > N || nextC < 1 || nextC > M || visited[nextR][nextC])
				continue;
			int nextTime = lake[nextR][nextC] ? time + 2 : time + 1;
			if (nextTime < fire[nextR][nextC]) {
				visited[nextR][nextC] = true;
				go(nextR, nextC, nextTime, collected + diamond[nextR][nextC]);
				visited[nextR][nextC] = false;
			}
	}
}


int main()
{	
	int T, tc;
	int sR, sC;
	int tmpR, tmpC;
	int lakeCnt, exitCnt, fireCnt;

	scanf("%d", &T);
	for (tc = 1; tc <= T; tc++) {
		rear = -1;
		front = 0;
		scanf("%d%d%d%d", &N, &M, &sR, &sC);

		for (int i = 1; i <= N; i++)
			for (int j = 1; j <= M; j++) {
				fire[i][j] = MAX_INT;
				lake[i][j] = exit[i][j] = visited[i][j] = false;
			}

		scanf("%d", &fireCnt);		
		for (int i = 0; i < fireCnt; i++) {
			scanf("%d%d", &tmpR, &tmpC);
			fire[tmpR][tmpC] = 0;
			Q[++rear] = tmpR * MAX_SIZE + tmpC;
		}

		scanf("%d", &lakeCnt);		
		for (int i = 0; i < lakeCnt; i++) {
			scanf("%d%d", &tmpR, &tmpC);
			lake[tmpR][tmpC] = true;
		}

		scanf("%d", &exitCnt);		
		for (int i = 0; i < exitCnt; i++) {
			scanf("%d%d", &tmpR, &tmpC);
			exit[tmpR][tmpC] = true;
		}

		for (int i = 1; i <= N; i++)
			for (int j = 1; j <= M; j++)
				scanf("%d", &diamond[i][j]);

		maxDiamond = -1;
		spreadFire();	
		visited[sR][sC] = true;

		go (sR, sC, 0, diamond[sR][sC]);

		printf("Case #%d\n%d\n", tc, maxDiamond);	
	}

	return 0;
}

Case #1
35
Case #2
102
Case #3
69
Case #4
172
Case #5
185
Case #6
219
Case #7
100
Case #8
538
Case #9
362
Case #10
342
Case #11
-1
Case #12
-1
Case #13
278
Case #14
2371
Case #15
866
Case #16
639
Case #17
856
Case #18
896
Case #19
1939
Case #20
1829
Case #21
3459
Case #22
794
Case #23
2237
Case #24
2375
Case #25
2897
Case #26
4979
Case #27
-1
Case #28
5123
Case #29
7052
Case #30
-1
Case #31
3742
Case #32
-1
Case #33
4483
Case #34
-1
Case #35
6129
Case #36
1259
Case #37
1109
Case #38
8367
Case #39
-1
Case #40
1046
Case #41
6467
Case #42
653
Case #43
3881
Case #44
624
Case #45
12412
Case #46
2132
Case #47
8878
Case #48
10177
Case #49
2727
Case #50
7216