杭二集训 三明治

搜索大法吼!

Posted by yjjr's blog on January 6, 2018

标签:dfs,bfs

题目

【题目背景】 你订购了 2nm 块三明治,并将它们摆成了一个 n×m 的矩形。 这里写图片描述 上图是 n = 2,m = 3 的一种可能的情况,可以看到,每两块三明治构成了一个正 方形。 你现在可以选择吃掉一些三明治。但为了避免麻烦,你希望每次吃的三明治都在边 界上。也就是说,你 . 不 . 能吃掉一块三明治当且仅当以下两个条件同时成立 • 这块三明治的斜边与某块未被吃掉的三明治相邻; • 这块三明之的至少一条直角边与某块未被吃掉的三明治相邻。 否则这块三明治可以被吃掉。 【题目描述】 现在你需要求出,对于每个小正方形内的两块三明治,要把它们都吃掉,至少需要 吃多少块三明治(包括这两块三明治本身)? 【输入格式】 从文件 sandwich.in 中读入数据。 输入第一行包含两个正整数 n,m,表示行数和列数。 接下来 n 行,每行 m 个字符,其中第 i 行第 j 个字符为 N 表示这个正方形内的两 块三明治的斜边沿主对角线放置,为 Z 表示沿副对角线放置。即这里写图片描述 【输出格式】 输出到文件 sandwich.out 中。 输出共 n 行,每行 m 个整数,第 i 行第 j 个整数表示吃掉位于第 i 行第 j 列的两 块三明治,至少需要吃多少块三明治。 如果这是不可能的,那么请在对应位置输出 −1。 【样例 1 输入】 2 3 NZN ZZN 【样例 1 输出】 10 8 2 8 6 4 【样例 2 输入】 2 2 NZ ZN 【样例 2 输出】 -1 -1 -1 -1 【样例 3 输入】 5 5 NZZZN NNNZN NNZNN NZNNN NZZZN 【样例 3 输出】 10 12 14 16 2 8 -1 -1 -1 4 6 -1 -1 -1 6 4 -1 -1 -1 8 2 16 14 12 10

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;
}

本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr