题解

提供一个并查集的做法(如有误欢迎大佬指出)

很明显棋盘是一个的矩阵,如果要阻断行走的路径,即将棋盘放置障碍物相当于斜切一刀,使棋盘分为左下和右上两个部分。
我们将四个边界分为两个部分,左边界和上边界分为一个部分(0表示),右边界和下边界分为一个部分(k+1表示)。如果实现分割的功能时,必然是这两个部分连接在了一起。

但是题目中又有限制,当移动坐标时只能向上或者向右移动,而不能向左向下移动。所以阻断的方法又增加了。
因此我们将要移除必须通过向下走或者向左走才能移除的路径

  • 向下走的情况

alt

如图所示,这是一种行不通的方案,但是同时黑方块也并没有相邻, 假设i为左边的黑方块,j为右边的黑方块,当i已经和k+1这部分连通,所以一定没有从下往上走的情况, 当同时满足x[ i ] < x[ j ] 和 y[ j ] <= y[ i ] + 1时,这两个黑方块部分也相当于连通

  • 向左走的情况

alt

原理与向下走的情况类似

AC代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N=3010;
int x[N],y[N];
int f[N];
bool st[N];
int find(int c){
    if(f[c]==c)return c;
    return f[c]=find(f[c]);
}
void unite(int a,int b){
    a=find(a);b=find(b);
    if(a==b)return;
    f[a]=b;
}
int main(){
    int n,m,k;
    queue<int>que;
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<=k+1;i++)f[i]=i;
    for(int i=1;i<=k;i++){
        scanf("%d%d",&x[i],&y[i]);
    }
    //从边界向内部延伸
    for(int i=1;i<=k;i++){
        if(x[i]==0||y[i]==m)unite(0,i),que.push(i),st[i]= true;
        if(y[i]==0||x[i]==n)unite(k+1,i),que.push(i),st[i]= true;
    }
    while(que.size()){
        int i=que.front();que.pop();
        for(int j=1;j<=k;j++){
            bool flag= false;
            if(abs(x[i]-x[j])<=1&&abs(y[i]-y[j])<=1)unite(i,j),flag= true;
            if(find(k+1)==find(i)&&x[i]<x[j]&&y[j]<=y[i]+1)unite(i,j),flag= true;
            if(find(0)==find(i)&&y[i]<y[j]&&x[j]<=x[i]+1)unite(i,j),flag= true;
            //假如没有添加进去过并且延伸到了,则加入队列中
            if(flag&&!st[j])que.push(j),st[j]= true;
        }
    }
    if(find(0)==find(k+1))printf("No");
    else printf("Yes");
    return 0;
}