解题思路

问题分析：

鼹鼠的初始位置不能在猎犬的初始位置或其相邻位置（曼哈顿距离 ≤$1$）。

在每个时间步，猎犬先移动（可能不动），然后鼹鼠移动（可能不动）。

鼹鼠在任何时候都不能被猎犬抓住（即鼹鼠的位置不能与猎犬或其相邻位置重合）。

需要模拟所有可能的时间步，逐步排除不可能的位置。

关键点：

鼹鼠的初始位置必须满足初始条件。

在每个时间步，鼹鼠的位置必须满足不被任何猎犬抓住。

鼹鼠的移动是动态的，需要跟踪所有可能的位置。

方法：

使用广度优先搜索（BFS）或集合操作来跟踪鼹鼠的可能位置。

对于每个时间步，先更新猎犬的位置，然后根据猎犬的位置排除鼹鼠的不可能位置。

最后剩下的位置就是鼹鼠的可能位置。

C++代码实现：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
#define mp make_pair
int W,L,T,N;
int Move[2][4] = { { -1 , 0 , 1 , 0 } , { 0 , 1 , 0 , -1 } };
 
bool cango[210][210][210];
bool vis[210][210][210];
struct Ans
{
        Ans(int xx = -1 , int yy = -1) : x (xx) , y (yy) { }
        int x , y;
}ans[110*110];
int top;
 
bool cmp(const Ans & a1 , const Ans & a2)
{
        if (a1.y==a2.y) return a1.x > a2.x;
        return a1.y > a2.y;
}
 
inline bool inRange(int r,int c)
{
        if (r < 0 || r > L || c < 0 || c > W) return false;
        return true;
}
 
 
void init()
{
        memset(cango,0x3f,sizeof(cango));
        memset(vis,0,sizeof(vis));
        top = 0;
}
 
void input()
{
        for (int i = 0 ; i < N ; ++i)
        {
                int r , c;
                for (int j = 0 ; j < T ; ++j)
                {
                        scanf("%d%d",&c,&r);
                        cango[j][r][c] = false;
                        for (int k = 0 ; k < 4 ; ++k)
                        {
                                int rr = r+Move[0][k];
                                int cc = c+Move[1][k];
                                if (!inRange(rr,cc)) continue;
                                cango[j][rr][cc] = false;
                        }
                }
        }
}
 
void dfs(int t,int r,int c)
{
        if (!cango[t+1][r][c] || vis[t][r][c]) return;
        if (t==T-1)
        {
                vis[t][r][c] = true;
                ans[top++] = Ans(c,r);
                return;
        }
        if (cango[t+1][r][c] && !vis[t+1][r][c]) dfs(t+1,r,c);
        for (int i = 0 ; i < 4 ; ++i)
        {
                int rr = r + Move[0][i];
                int cc = c + Move[1][i];
                if (!inRange(rr,cc) || !cango[t+1][rr][cc] || vis[t+1][rr][cc]) continue;
                dfs(t+1,rr,cc);
        }
        vis[t][r][c] = true;
}
 
void solve()
{
        for (int r = 0 ; r <= L ; ++r)
        {
                for (int c = 0 ; c <= W ; ++c) if (cango[0][r][c])
                {
                        dfs(0,r,c);
                }
        }
        sort(ans,ans+top,cmp);
        int cnt = 0;
        if (top)
        {
                Ans tmp = Ans(-1,-1);
                while (top)
                {
                        tmp = ans[--top];
                        if (cnt) printf(" ");
                        printf("(%d,%d)",tmp.x,tmp.y);
                        ++cnt;
                        if (cnt==8) 
                        {
                                printf("\n");
                                cnt = 0;
                        }
                }
        }
        else 
                printf("No possible locations\n");
        if (cnt) cout << endl;
}
 
int main()
{
        int Cas = 0;
        while (scanf("%d%d%d%d",&W,&L,&N,&T) , N+T+W+L)
        {
                ++Cas;
                init();
                input();
                printf("Observation Set %d\n",Cas);
                solve();
        }
}