自动搬运

查看原文

来自洛谷，原作者为

	施玮宸SECSA **

搬运于2025-08-24 22:02:18，当前版本为作者最后更新于2020-01-02 21:19:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

第一次在做这道题时：
whaaaat?什么题目？
但是，这题真有那么难吗?????????
经过一定思考后，发现该题其实就是一个BFS。此题并没有边权的一定限制，却有一个边的颜色（黑，白，也有可能没有颜色）
那么这题是不是一个奇偶最短路（用广度优先搜索来求解）呢？？？？？？ 经过分析，发现的确如此。
需要记录走过的边的号码。
复杂度：$O(ts)$~~~~~~~

前方贴出代码

#include<bits/stdc++.h>
using namespace std;
const int max_n=1000001,max_m=2000001;
const int max_e=5000001;
struct node{
	int t;
	int w;
	int n;
};//用于链表的结构体
node e[max_e];
bool bl[2][max_n];
int now[max_m],ret[max_m],h[max_m],m;
void a(int x,int y,int z){
	e[++m].w=z;
	e[m].t=y;
	e[m].n=h[x];
	h[x]=m;//链表增边
}
int x,y,xx,yy;
int s,t,u,v;
int le,ri;//左，右
int tmp,rem,res;
char c;//读入的字符
int main(){
	ri=tmp=2;
	cin>>t>>s>>x>>y>>xx>>yy;
	for(int i=1;i<=((s*2)|1);i++){
		c=getchar();//读入
		for(int j=1;j<=((i&1)?t:((t*2)|1));j++){
			c=getchar();//读入
			if('n'==c) continue;
			if((i&1)!=0){
				u=(t+1)*(i/2)+j;
				v=u+1;
			}
			else{
				u=(t+1)*(i/2)+(j/2)+(1&j);
				v=u-(1&j)-t;
			}
			a(v,u,!(c=='w'));
			a(u,v,!(c=='w'));
		}
	}
   	//上边是所有的输入&预处理~~~
	now[2]=now[1]=x+1+(t+1)*y;
	ret[1]=0;
	res=0;
	rem=xx+1+(t+1)*yy;
	ret[2]=le=1;
	bl[1][now[1]]=1;
	bl[0][now[1]]=1;
	while(ri>=le){
		if(rem==now[le]){
			break;
		}
		for(int i=h[now[le]];i;i=e[i].n){
			if(e[i].w!=ret[le]){
				v=e[i].t;
				if(bl[e[i].w][v]==0){
					now[++ri]=v;
					bl[e[i].w][v]=1;
					ret[ri]=e[i].w;
				}
			}
		}
		le++;
		if(tmp<le){
			res++;
			tmp=ri;
		}
	}
    	//????上面是整个bfs~
	cout<<res<<endl;//最后输出
	return 0;
}

感谢观看。