大家好，又见面了，我是全栈君，今天给大家准备了Idea注册码。
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;}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/117883.html原文链接：https://javaforall.net
