Untitled
unknown
plain_text
2 years ago
1.7 kB
3
Indexable
#include <stdio.h> #define MAX_N 3000 #define INF 1000000000 #define EMPTY 1000000001 #define MAX_STEP 101 int map[MAX_N][MAX_N]; int N, M; int boundCnt; int remain; //Queue int Q[MAX_N * MAX_N]; int front, rear; int dy[] = {0, 1, 0, -1}; int dx[] = {1, 0, -1, 0}; int emptyTime, maxTime; void BFS(int r, int c) { front = rear = 0; Q[0] = r * M + c; int nextR, nextC; --remain; while (front <= rear) { r = Q[front] / M; c = Q[front++] % M; for (int d = 0; d < 4; d++) { nextR = r + dy[d]; nextC = c + dx[d]; if (nextR < 0 || nextR == N || nextC < 0 || nextC == M || map[nextR][nextC] == -1) continue; if (map[nextR][nextC] <= map[r][c] + 1) continue; if (map[nextR][nextC] == EMPTY) { boundCnt--; if (boundCnt == 0) { map[nextR][nextC] = map[r][c]; --remain; emptyTime = map[nextR][nextC]; } } else { map[nextR][nextC] = map[r][c] + 1; --remain; Q[++rear] = nextR * M + nextC; if (map[nextR][nextC] > maxTime) maxTime = map[nextR][nextC]; } } } } int main() { int tc, T; int sR, sC; scanf("%d", &T); for (tc = 1; tc <= T; tc++) { scanf("%d%d", &N, &M); scanf("%d%d", &sR, &sC); sR--; sC--; remain = N * M; boundCnt = 4; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { scanf("%d", &map[i][j]); if (map[i][j] == 0) { map[i][j] = -1; remain--; } else map[i][j] += INF - 1; } } emptyTime = maxTime = -1; map[sR][sC] = 1; BFS(sR, sC); if (remain) maxTime = -1; printf("Case #%d\n%d %d\n", tc, emptyTime, maxTime); } return 0; }
Editor is loading...