/* 怎么建图: 首先分集合:不能相连的点必然在一个集合里,即对角点 再确定怎么连边: 一个点可以向上下左右连边,如果遇到了洞则不行 dfs(i),让匹配到的点接受i作为match结果 寻找增广路时,要让v接受i,那么v原来接受的点match[v]就要重新找一个点进行匹配 */ #include<iostream> #include<cstring> #include<cstdio> using namespace std; #define maxn 2500 int n,m,k,hole[100][100],mp[maxn][maxn],id[maxn][maxn]; int vis[maxn],cnt,match[maxn]; int dfs(int x){ for(int i=1;i<=cnt;i++) if(mp[x][i] && !vis[i]){ vis[i]=1; if(!match[i] || dfs(match[i])){//寻找增广路 match[i]=x;return 1; } } return 0; } void init(){ cnt=0; memset(match,0,sizeof match); memset(hole,0,sizeof hole); memset(mp,0,sizeof mp); memset(id,0,sizeof id); } int main(){ init(); cin>>m>>n>>k; for(int i=1;i<=k;i++){ int x,y; cin>>x>>y; hole[y][x]=1; } //给每个点重定义标记 for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) if(!hole[i][j])id[i][j]=++cnt; //建图 for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) if(!hole[i][j]) { if(i-1>=1 && !hole[i-1][j]) mp[id[i][j]][id[i-1][j]]=1; if(i+1<=m && !hole[i+1][j]) mp[id[i][j]][id[i+1][j]]=1; if(j-1>=1 && !hole[i][j-1]) mp[id[i][j]][id[i][j-1]]=1; if(j+1<=n && !hole[i][j+1]) mp[id[i][j]][id[i][j+1]]=1; } int ans=0; for(int i=1;i<=cnt;i++){ memset(vis,0,sizeof vis); if(dfs(i))++ans; } if(ans==cnt)puts("YES"); else puts("NO"); }