题意：在一个方阵中，一个强盗犯要逃跑。你是警察要去抓他，现在你手上有若干线索他们会告诉你第i时刻一个方阵中他们没有看见强盗。在t秒后全部道路会*。让你通过线索来判断是不是能够找到小偷在某一秒的位置。
思路：最先想到的思路就是记忆化搜索，但是可惜状态想错了，没有成功。然后又尝试了若干种方法都没有成功。最后去看解题报告才明白了。状态信息不唯一需要三维dp[i][j][k]表示在（i,j）t时刻有没有可能出现强盗。然后我们在搜索过程中用ans[i]记录i时刻能出现的位置，最后若是唯一就可以输出。
代码如下：
1 /************************************************** 2 * author : xiaohao z 3 * blog : http://www.cnblogs.com/shu-xiaohao/ 4 * last modified : 2014-01-27 10:57 5 * filename : uva_707.cpp 6 * description : 7 * ************************************************/ 8 9 #include <iostream> 10 #include <cstdio> 11 #include <cstring> 12 #include <cstdlib> 13 #include <cmath> 14 #include <algorithm> 15 #include <queue> 16 #include <stack> 17 #include <vector> 18 #include <set> 19 #include <map> 20 #define MP(a, b) make_pair(a, b) 21 #define PB(a) push_back(a) 22 23 using namespace std; 24 typedef long long ll; 25 typedef pair<int, int> pii; 26 typedef pair<unsigned int,unsigned int> puu; 27 typedef pair<int, double> pid; 28 typedef pair<ll, int> pli; 29 typedef pair<int, ll> pil; 30 31 const int INF = 0x3f3f3f3f; 32 const double eps = 1e-6; 33 const int LEN = 102; 34 int dp[LEN][LEN][LEN], kase = 1, n, m, t, cnt; 35 int xx[] = {0, 0, 1,-1, 0}; 36 int yy[] = {1,-1, 0, 0, 0}; 37 vector<pii> ans[LEN]; 38 39 int dfs(int x, int y, int tt){ 40 if(dp[x][y][tt] != -1) return dp[x][y][tt]; 41 if(tt>=t){ 42 cnt ++; 43 ans[t].PB(MP(x, y)); 44 return dp[x][y][t] = 1; 45 } 46 dp[x][y][tt] = 0; 47 for(int i=0; i<5; i++){ 48 int tx = x+xx[i]; 49 int ty = y+yy[i]; 50 if(tx>0 && tx<=n && ty>0 && ty<=m){ 51 if(dfs(tx, ty, tt+1)) dp[x][y][tt] = 1; 52 } 53 } 54 if(dp[x][y][tt]){ 55 ans[tt].PB(MP(x, y)); 56 } 57 return dp[x][y][tt]; 58 } 59 60 int main() 61 { 62 //freopen("in.txt", "r", stdin); 63 int a, b, c, d, q, tt; 64 while(scanf("%d%d%d", &n, &m, &t)!=EOF){ 65 if(!n && !m && !t) break; 66 for(int i=0; i<LEN; i++)ans[i].clear();cnt=0; 67 scanf("%d", &q); 68 memset(dp, -1, sizeof dp); 69 for(int i=0; i<q; i++) { 70 scanf("%d%d%d%d%d", &tt, &a, &b, &c, &d); 71 for(int j=a; j<=c; j++){ 72 for(int k=b; k<=d; k++){ 73 dp[j][k][tt] = 0; 74 } 75 } 76 } 77 for(int i=1; i<=n; i++){ 78 for(int j=1; j<=m; j++){ 79 if(dp[i][j][1]<0)dfs(i, j, 1); 80 } 81 } 82 printf("Robbery #%d:\n", kase++); 83 if(cnt == 0) printf("The robber has escaped.\n"); 84 else { 85 int f = 1; 86 for(int i=1; i<=t; i++){ 87 if(ans[i].size()==1){ 88 f = 0; 89 printf("Time step %d: The robber has been at %d,%d.\n", i, ans[i][0].first, ans[i][0].second); 90 } 91 } 92 if(f) printf("Nothing known.\n"); 93 } 94 printf("\n"); 95 } 96 return 0; 97 }