Untitled
unknown
plain_text
2 years ago
3.3 kB
3
Indexable
#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
Editor is loading...