算法标签：

模拟

题解：

数据范围不大， W, H, t (1 <= W,H,t <= 100)。于是决定暴力解决。

先根据读入的ti, Li, Ti, Ri, Bi信息初始化大盗不可能存在的位置not_visit[t][x][y]。之后使用类此floodfill的思路，分别用按t正推和按t逆推将not_visit[t][x][y]填好。

之后对每一时刻t，统计not_visit[t][x][y]==0（即大盗可能存在位置）的数量记为tmp。若某一个时刻tmp == 0则大盗逃出去了，输出escape。若tmp == 1则在这一时刻可以确定大盗的位置。

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 110

int W, H, T, n;
bool notv[maxn][maxn][maxn];

bool cant(int t, int x, int y, int tadd)
{
    if (x>0 &&!notv[t+tadd][x-1][y]) return false;
    if (x<W-1 &&!notv[t+tadd][x+1][y]) return false;
    if (y>0 &&!notv[t+tadd][x][y-1]) return false;
    if (y<H-1 &&!notv[t+tadd][x][y+1]) return false;
    if (!notv[t+tadd][x][y]) return false;
    return true; 
}

int main()
{
    int cs=0, t, x1, y1, x2, y2;
    int maybe[maxn], xx[maxn], yy[maxn];
    bool escape, know;
    
    while (cin >> W >> H >> T && W && H && T)
    {
        cout << "Robbery #" << ++cs << ":" << endl;
        cin >> n;
        memset(notv, 0, sizeof(notv));
        memset(maybe, 0, sizeof(maybe));
        escape=false;
        for (int i=0; i<n; i++)
        {
            cin >> t >> x1 >> y1 >> x2 >> y2;
            for (int x=x1-1; x<x2; x++)         //根据输入判断强盗肯定不在的位置 
                for (int y=y1-1; y<y2; y++)
                    notv[t-1][x][y]=true;
        }
        for (int t=1; t<T; t++)                             //正着一遍floodfill强盗肯定不在的位置 
            for (int x=0; x<W; x++)
                for (int y=0; y<H; y++)
                    if (!notv[t][x][y] && cant(t, x, y, -1))
                        notv[t][x][y]=true;
        
        for (int x=0; x<W; x++)
            for (int y=0; y<H; y++)
            {
                if (!notv[T-1][x][y])
                {
                    maybe[T-1]++; xx[T-1]=x; yy[T-1]=y;
                }
            }
        if (maybe[T-1]==0) escape=true;                      //判断最后时刻是否逃走，是的话结束 
        for (int t=T-2; t>=0 &&!escape; t--)                 //反着一遍floodfill强盗肯定不在的位置
        {
            for (int x=0; x<W; x++)
                for (int y=0; y<H; y++)
                {
                    if (!notv[t][x][y] && cant(t, x, y, +1))
                        notv[t][x][y]=true;
                    if (!notv[t][x][y])
                    {
                        maybe[t]++; xx[t]=x; yy[t]=y;
                    }
                }
            if (maybe[t]==0) escape=true;
        }
        if (escape)
            cout << "The robber has escaped." << endl << endl;
        else
        {
            know=false;
            for (int t=0; t<T; t++)
                if (maybe[t]==1)
                {
                    know=true;
                    cout << "Time step " << t+1 << ": The robber has been at " << xx[t]+1 << "," << yy[t]+1 << "." << endl;
                }
            if (!know) cout << "Nothing known." << endl;
            cout << endl;
        }
    }
    return 0;
}