UVA 707 - Robbery（記憶化搜索)
來源：程序員人生 發(fā)布時間：2014-09-01 09:04:40 閱讀次數(shù)：2756次
UVA 707 - Robbery
題目鏈接
題意：在一個w * h的圖上，t個時刻，然后知道一些信息，每個時刻沒有小偷的矩陣位置，問哪些時刻可以唯一確定小偷位置，和確定小偷是否已經(jīng)逃走，如果沒逃走，但是也沒有時刻可以可以確定小偷位置，就是不知到
思路：記憶化搜索，dp[x][y][ti]表示在x，y位置，ti時刻時候，小偷是否可能出現(xiàn)在這個位置，1表示有可能，0表示沒可能，由于小偷一次最多只能上下左右走一步或者不走，所以去dfs一遍即可
最后判斷的時候，如果有一個時刻沒有一個1，就表示已經(jīng)逃走，如果所有時刻的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.
", 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:
", ++cas);
int tmp = solve();
if (tmp == 0) printf("The robber has escaped.
");
else if (tmp == 1) printf("Nothing known.
");
printf("
");
}
return 0;
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈
