1488.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1488 on 2006-02-21 at 21:19:45 */ 
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

typedef pair<int, int> pii;
const int MAX = 128;
const int DIR[][2] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };

char map[MAX][MAX];
int n, m, step[MAX][MAX];
queue<pii> Q;

void DFS(int, int, int);

int main()
{
	int i, case_no;
	
	for(case_no = 1; scanf("%d %d\n", &n, &m) != EOF && n != 0; case_no++) {
		for(i = 0; i < n; i++) gets(map[i]);
		memset(step, -1, sizeof(step));
		while(!Q.empty()) Q.pop();
		DFS(0, 0, 0);
		while(!Q.empty()) {
			pii p = Q.front(); Q.pop();
			int px = p.first >> 8, py = p.first & 127;
			DFS(px, py, p.second);
		}
		printf("Case %d:\n", case_no);
		int t, T;
		scanf("%d", &T);
		for(t = 0; t < T; t++) {
			int x, y; scanf("%d %d", &x, &y);
			if(step[x][y] == 0) printf("It's dangerous!\n");
			else printf("It's safe with at least %d missile defences!\n", step[x][y]);
		}
	}
	
	return 0;
}

void DFS(int x, int y, int k)
{
	int i, stack[MAX*MAX], top = 0;
	step[x][y] = k; stack[top++] = (x << 8) + y;
	while(top != 0) {
		int p = stack[--top], px = p >> 8, py = p & 127;
		for(i = 0; i < 4; i++) {
			int cx = px + DIR[i][0], cy = py + DIR[i][1];
			if(cx < 0 || cx >= n || cy < 0 || cy >= m || step[cx][cy] != -1) continue;
			if(map[cx][cy] == '0') { step[cx][cy] = k; stack[top++] = (cx << 8) + cy; }
			else { step[cx][cy] = k+1; Q.push(pii((cx<<8)+cy, k+1)); }
		}
	}
}