UVA 707 - Robbery

题目链接

题意：在一个w * h的图上，t个时刻，然后知道一些信息，每个时刻没有小偷的矩阵位置，问哪些时刻可以唯一确定小偷位置，和确定小偷是否已经逃走，如果没逃走，但是也没有时刻可以可以确定小偷位置，就是不知到

思路：记忆化搜索，dp[x][y][ti]表示在x，y位置，ti时刻时候，小偷是否可能出现在这个位置，1表示有可能，0表示没可能，由于小偷一次最多只能上下左右走一步或者不走，所以去dfs一遍即可

最后判断的时候，如果有一个时刻没有一个1，就表示已经逃走，如果所有时刻的1都超过1个，那么就是不知道，其他就可以确定答案

代码：

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

const int N = 105;
const int d[5][2] = {{0, 0}, {0, 1}, {0, -1}, {1, 0}, {-1, 0}};
typedef pair<int, int> pii;

int w, h, t, n;
int dp[N][N][N];
vector<pii> ans[N];

void init() {
	scanf("%d", &n);
	int ti, xa, ya, xb, yb;
	memset(dp, -1, sizeof(dp));
	while (n--) {
		scanf("%d%d%d%d%d", &ti, &xa, &ya, &xb, &yb);
		for (int i = xa; i <= xb; i++)
			for (int j = ya; j <= yb; j++)
				dp[i][j][ti] = 0;
	}
}

int dfs(int x, int y, int ti) {
	int &ans = dp[x][y][ti];
	if (ans != -1) return ans;
	ans = 0;
	if (ti == t) return ans = 1;
	for (int i = 0; i < 5; i++) {
		int xx = x + d[i][0];
		int yy = y + d[i][1];
		if (xx < 1 || xx > w || yy < 1 || yy > h) continue;
		if (dfs(xx, yy, ti + 1))
			ans = 1;
	}
	return ans;
}

int solve() {
	int flag;
	for (int i = 1; i <= t; i++) {
		ans[i].clear();
		flag = 0;
		for (int j = 1; j <= w; j++)
			for (int k = 1; k <= h; k++) {
				if (dp[j][k][i] == 1) {
					ans[i].push_back(make_pair(j, k));
					flag = 1;
				}
			}
		if (flag == 0) return 0;
	}
	flag = 1;
	for (int i = 1; i <= t; i++) {
		if (ans[i].size() == 1) {
			printf("Time step %d: The robber has been at %d,%d.\n", i, ans[i][0].first, ans[i][0].second);
			flag = 0;
		}
	}
	if (flag) return 1;
	return 2;
}

int main() {
	int cas = 0;
	while (~scanf("%d%d%d", &w, &h, &t) && w) {
		init();
		for (int i = 1; i <= w; i++)
			for (int j = 1; j <= h; j++)
				dfs(i, j, 1);
		printf("Robbery #%d:\n", ++cas);
		int tmp = solve();
		if (tmp == 0) printf("The robber has escaped.\n");
		else if (tmp == 1) printf("Nothing known.\n");
		printf("\n");
	}
	return 0;
}

UVA 707 - Robbery（记忆化搜索)