Untitled

 avatar
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...