题意：一个n*m的城市，有小偷会偷银行，小偷偷东西t分钟后，城市会被全部封锁，然后会有q次排查，每次排查的范围是一个矩形，给出左上角坐标（a,b)和右下角坐标(c,d)，格式为t a,b,c,d，表示这个范围该时间小偷不再，输出所有小偷可能在的位置和时间
分析：一共有三种情况，确定小偷所在的位置和时间，小偷逃离城市，一无所获，要描述一个状态，至少要有三个量，(x,y,t),因为不知道小偷在哪，所以要尝试t=1的时候小偷所有可能的位置，-1表示该状态还未确定，0表示不在，1表示可能在，那么从开始搜就行了,如果一个状态的后继状态不全部在不可能区域，说明他可能在该位置，记录每个时间可能的坐标，如果一个时间可能的坐标只有一个，那么久确定了小偷的位置
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; const int maxn=105; int dp[maxn][maxn][maxn]; int n,m,t,cnt; int dx[]={0, 0, 1,-1, 0}; int dy[]={1,-1, 0, 0, 0}; struct node{ int x,y; node(){} node(int a,int b):x(a),y(b){} }; vector<node> ans[maxn]; int dfs(int x, int y, int tt){ if(dp[x][y][tt] != -1) return dp[x][y][tt]; if(tt>=t){ cnt ++; ans[t].push_back(node(x,y)); return dp[x][y][t] = 1; } dp[x][y][tt] = 0; for(int i=0; i<5; i++){ int tx = x+dx[i]; int ty = y+dy[i]; if(tx>0 && tx<=n && ty>0 && ty<=m){ if(dfs(tx, ty, tt+1)) dp[x][y][tt] = 1; } } if(dp[x][y][tt]){ ans[tt].push_back(node(x,y)); } return dp[x][y][tt]; } int main(){ int cas=1; while(~scanf("%d%d%d",&n,&m,&t)&&n+m+t){ int q; scanf("%d",&q); cnt=0; memset(dp,-1,sizeof(dp)); for(int i=0;i<maxn;i++)ans[i].clear(); int tt,a,b,c,d; while(q--){ scanf("%d%d%d%d%d",&tt,&a,&b,&c,&d); for(int i=a;i<=c;i++) for(int j=b;j<=d;j++) dp[i][j][tt]=0; } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(dp[i][j][1]<0) dfs(i,j,1); printf("Robbery #%d: ",cas++); if(cnt==0) printf("The robber has escaped. "); else{ bool ok=1; for(int i=1;i<=t;i++) if(ans[i].size()==1){ ok=0; printf("Time step %d: The robber has been at %d,%d. ", i, ans[i][0].x, ans[i][0].y); } if(ok) printf("Nothing known. "); } puts(""); } return 0; }