标签：dfs，bfs
题目
【题目背景】 你订购了 2nm 块三明治，并将它们摆成了一个 n×m 的矩形。
N<=400
分析
肥宅大爷先瞎说了一堆物理性质：什么把这些全看成玻璃，产生漫反射，然后想象光线乱搞，真的很佩服这种有理有据地瞎扯，果然是大爷%%%
虽然那种做法最后凉凉，MLE&&TLE
我先写了35分的暴搜bfs，代码真丑真长啊qwq（4K）
从四角暴搜
如上图，正确的搜索姿势是这样子的
可以判断出答案在一定范围内具有单调性的
我们就要可以从边界沿着每个方向去dfs搜索，只需要搜索一次
code
35分丑暴力
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define inf 0x3f3f3f
using namespace std;
inline ll read()
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=106;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
int n,m;
int Map[maxn][maxn],t[maxn][maxn],ans[maxn][maxn];
struct node{int x,y;}que[maxn<<1];
char ch;
inline bool pz(int x,int y){
if(x<1||x>n||y<1||y>m||t[x-1][y]!=0||t[x][y-1]!=0||t[x][y]!=2)return 0;
}
inline bool pn(int x,int y){
if(x<1||x>n||y<1||y>m||t[x+1][y]!=0||t[x][y+1]!=0||t[x][y]!=1)return 0;
}
int main()
{
n=read(),m=read();
mem(ans,inf);
rep(i,1,n)
rep(j,1,m){
cin>>ch;
if(ch=='N')Map[i][j]=1;else Map[i][j]=2;
}
if(Map[1][1]==2){
memcpy(t,Map,sizeof Map);mem(que,0);
int head=0,tail=1,now=2;
que[0].x=1,que[0].y=1;
ans[1][1]=2;
while(head<tail){
t[que[head].x][que[head].y]=0;
rep(i,0,3){
int nowx=que[head].x+dx[i],nowy=que[head].y+dy[i];
if(pz(nowx,nowy))
if(ans[nowx][nowy]>=ans[que[head].x][que[head].y]+2){
que[tail++]=(node){nowx,nowy};
ans[nowx][nowy]=ans[que[head].x][que[head].y]+2;
}
}
if(pz(que[head].x+1,que[head].y)){
que[tail++]=(node){que[head].x+1,que[head].y};
ans[que[head].x+1][que[head].y]=min(ans[que[head].x+1][que[head].y],ans[que[head].x][que[head].y]+2);
}
if(pz(que[head].x,que[head].y+1)){
que[tail++]=(node){que[head].x,que[head].y+1};
ans[que[head].x][que[head].y+1]=min(ans[que[head].x][que[head].y+1],ans[que[head].x][que[head].y]+2);
}
head++;
}
}
if(Map[n][m]==2){
memcpy(t,Map,sizeof Map);mem(que,0);
int head=0,tail=1,now=2;
que[0].x=n,que[0].y=m;
ans[n][m]=2;
while(head<tail){
t[que[head].x][que[head].y]=0;
if(pz(que[head].x-1,que[head].y)){
que[tail++]=(node){que[head].x-1,que[head].y};
ans[que[head].x-1][que[head].y]=min(ans[que[head].x-1][que[head].y],ans[que[head].x][que[head].y]+2);
}
if(pz(que[head].x,que[head].y-1)){
que[tail++]=(node){que[head].x,que[head].y-1};
ans[que[head].x][que[head].y-1]=min(ans[que[head].x][que[head].y-1],ans[que[head].x][que[head].y]+2);
}
head++;
}
}
if(Map[1][m]==1){
memcpy(t,Map,sizeof Map);mem(que,0);
int head=0,tail=1,now=2;
que[0].x=1,que[0].y=m;
ans[1][m]=2;
while(head<tail){
t[que[head].x][que[head].y]=0;
if(pn(que[head].x+1,que[head].y)){
que[tail++]=(node){que[head].x+1,que[head].y};
ans[que[head].x+1][que[head].y]=min(ans[que[head].x+1][que[head].y],ans[que[head].x][que[head].y]+2);
}
if(pn(que[head].x,que[head].y-1)){
que[tail++]=(node){que[head].x,que[head].y-1};
ans[que[head].x][que[head].y-1]=min(ans[que[head].x][que[head].y-1],ans[que[head].x][que[head].y]+2);
}
head++;
}
}
if(Map[n][1]==1){
memcpy(t,Map,sizeof Map);mem(que,0);
int head=0,tail=1,now=2;
que[0].x=n,que[0].y=1;
ans[n][1]=2;
while(head<tail){
t[que[head].x][que[head].y]=0;
if(pn(que[head].x-1,que[head].y)){
que[tail++]=(node){que[head].x-1,que[head].y};
ans[que[head].x-1][que[head].y]=min(ans[que[head].x-1][que[head].y],ans[que[head].x][que[head].y]+2);
}
if(pn(que[head].x,que[head].y+1)){
que[tail++]=(node){que[head].x,que[head].y+1};
ans[que[head].x][que[head].y+1]=min(ans[que[head].x][que[head].y+1],ans[que[head].x][que[head].y]+2);
}
head++;
}
}
rep(i,1,n){
rep(j,1,m)if(ans[i][j]<inf)cout<<ans[i][j]<<' ';else cout<<"-1 ";
cout<<endl;
}
return 0;
}
标程
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define inf 1e9
using namespace std;
inline ll read()
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=406;
int n,m,vis[maxn][maxn],ans[maxn][maxn];
char st[maxn][maxn];
int dfs(int x,int y,int flag){
if(vis[x][y]==1)return inf;
if(vis[x][y]==2)return 0;
int cnt=2;
vis[x][y]=1;
if(!flag){
if(st[x][y]=='N'){
if(x!=n)cnt+=dfs(x+1,y,flag^(st[x+1][y]!=st[x][y]));
if(y!=1)cnt+=dfs(x,y-1,flag);
}else{
if(x!=1)cnt+=dfs(x-1,y,flag&(st[x-1][y]!=st[x][y]));
if(y!=1)cnt+=dfs(x,y-1,flag);
}
}else{
if(st[x][y]=='N'){
if(x!=1)cnt+=dfs(x-1,y,flag^(st[x-1][y]!=st[x][y]));
if(y!=m)cnt+=dfs(x,y+1,flag);
}else{
if(x!=n)cnt+=dfs(x+1,y,flag^(st[x+1][y]!=st[x][y]));
if(y!=m)cnt+=dfs(x,y+1,flag);
}
}
vis[x][y]=2;
return cnt<inf?cnt:inf;
}
int main()
{
n=read(),m=read();
rep(i,1,n)scanf("%s",st[i]+1);
rep(i,1,n)rep(j,1,m)ans[i][j]=inf;
rep(i,1,n)
rep(flag,0,1){
mem(vis,0);
int re=0;
rep(j,1,m){
int k=j;
if(flag)k=m-j+1;
re+=dfs(i,k,flag);
if(re>=inf)break;
ans[i][k]=min(ans[i][k],re);
}
}
rep(i,1,n){
rep(j,1,m)if(ans[i][j]<inf)cout<<ans[i][j]<<' ';else cout<<"-1 ";
cout<<endl;
}
return 0;
}
