题解 AT1829 【サンドイッチ】
jun头吉吉
·
·
题解
\text{更不行的阅读体验}
题意
你现在可以选择吃掉一些三明治，每次吃的三明治都必须在边界上。更具体地， 你不能吃掉一块三明治当且仅当以下两个条件同时成立：
1. 这块三明治的斜边与某块未被吃掉的三明治相邻；
2. 这块三明治的至少一条直角边与某块未被吃掉的三明治相邻。
请你求出，对于每个小正方形内的两块三明治，要把它们全部吃掉，至少需要吃多少块三明治。
## 题解
首先我们不难发现，如果一个小正方形钦定左边的小三角形先取，那么与右边的小三角形相连的两个三角形也必须是那个正方形里先删除的。
用 $\rm dfs$ 爆搜上面的过程，如果一个正方形左边的先删除并且右边的先删除那么显然无解，如果搜索的过程中出现了环那么也是无解。否则个数就是搜索过程中搜到的点 $\times 2$。
现在是 $\mathcal O(n^2m^2)$ 的，但是我们发现如果钦定某一个位置左边的三角形先取，那么的点必然包含右边的正方形的左边的三角形需要的。所以可以直接在左边的基础上继续 $\rm dfs$，复杂度降为 $\mathcal O(n^2m)$。
## 代码
丑得要死仅供参考。
```cpp
#include<bits/stdc++.h>
#define pb push_back
#define chkmx(a,b) ((a)=max((a),(b)))
#define chkmn(a,b) ((a)=min((a),(b)))
using namespace std;
template<typename T>
inline void read(T &x){x=0;char c=getchar();bool f=false;for(;!isdigit(c);c=getchar())f|=c=='-';for(;isdigit(c);c=getchar())x=x*10+c-'0';if(f)x=-x;}
template<typename T ,typename ...Arg>inline void read(T &x,Arg &...args){read(x);read(args...);}
template<typename T>inline void write(T x){if(x<0)putchar('-'),x=-x;if(x>=10)write(x/10);putchar(x%10+'0');}
//#define int long long
typedef long long ll;
const int N=410;
#define l 0
#define r 1
#define u 2
#define d 3
const int dx[4]={0,0,-1,1};
const int dy[4]={-1,1,0,0};
int n,m;char mp[N][N];
namespace solve0{
//暴力bfs
bool flag[N][N][4];
bool vis[N][N];bool ins[N][N];
queue<pair<int,int>>q;int tot;
int ans[N][N];
bool chk(int x,int y){
if(mp[x][y]=='N'){
if((flag[x][y][l]||flag[x][y][d])&&(flag[x][y][r]||flag[x][y][u]))return false;
return true;
}else if(mp[x][y]=='Z'){
if((flag[x][y][l]||flag[x][y][u])&&(flag[x][y][r]||flag[x][y][d]))return false;
return true;
}
}
void dfs(int x,int y){
if(ins[x][y])tot=0x3f3f3f3f;
if(tot==0x3f3f3f3f)return;
if(vis[x][y])return;
vis[x][y]=1;ins[x][y]=1;
tot++;
assert(chk(x,y));
if(mp[x][y]=='N'){
// (l,d) (r,u)
if(flag[x][y][l]||flag[x][y][d]){
assert(!flag[x][y][r]&&!flag[x][y][u]);
for(int i=0;i<4;i++)if(i==r||i==u){
int xx=x+dx[i];
int yy=y+dy[i];
if(xx<1||xx>n||yy<1||yy>m)continue;
flag[xx][yy][i^1]=1;
if(!chk(xx,yy)){
tot=0x3f3f3f3f;
return;
}
dfs(xx,yy);
}
}else if(flag[x][y][r]||flag[x][y][u]){
assert(!flag[x][y][l]&&!flag[x][y][d]);
for(int i=0;i<4;i++)if(i==l||i==d){
int xx=x+dx[i];
int yy=y+dy[i];
if(xx<1||xx>n||yy<1||yy>m)continue;
flag[xx][yy][i^1]=1;
if(!chk(xx,yy)){
tot=0x3f3f3f3f;
return;
}
dfs(xx,yy);
}
}
}else{
// (l,u) (r,d)
if(flag[x][y][l]||flag[x][y][u]){
assert(!flag[x][y][r]&&!flag[x][y][d]);
for(int i=0;i<4;i++)if(i==r||i==d){
int xx=x+dx[i];
int yy=y+dy[i];
if(xx<1||xx>n||yy<1||yy>m)continue;
flag[xx][yy][i^1]=1;
if(!chk(xx,yy)){
tot=0x3f3f3f3f;
return;
}
dfs(xx,yy);
}
}else if(flag[x][y][r]||flag[x][y][d]){
assert(!flag[x][y][l]&&!flag[x][y][u]);
for(int i=0;i<4;i++)if(i==l||i==u){
int xx=x+dx[i];
int yy=y+dy[i];
if(xx<1||xx>n||yy<1||yy>m)continue;
flag[xx][yy][i^1]=1;
if(!chk(xx,yy)){
tot=0x3f3f3f3f;
return;
}
dfs(xx,yy);
}
}
}
ins[x][y]=0;
}
void work(){
memset(ans,0x3f,sizeof ans);
for(int i=1;i<=n;i++){
memset(flag,0,sizeof flag);
memset(vis,0,sizeof vis);
memset(ins,0,sizeof ins);
tot=0;
for(int j=1;j<=m;j++){
flag[i][j][r]=1;
if(!chk(i,j))tot=0x3f3f3f3f;
dfs(i,j);
chkmn(ans[i][j],tot);
}
}
for(int i=1;i<=n;i++){
memset(flag,0,sizeof flag);
memset(vis,0,sizeof vis);
memset(ins,0,sizeof ins);
tot=0;
for(int j=m;j;j--){
flag[i][j][l]=1;
if(!chk(i,j))tot=0x3f3f3f3f;
dfs(i,j);
chkmn(ans[i][j],tot);
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
write(ans[i][j]==0x3f3f3f3f?-1:ans[i][j]*2),putchar(" \n"[j==m]);
}
}
signed main(){
//freopen("C.in","r",stdin);
//freopen("C.out","w",stdout);
read(n,m);
for(int i=1;i<=n;i++)
scanf("%s",mp[i]+1);
solve0::work();
}
```