【洛谷算法1-7】【搜索DFS】习题解析

目录

[USACO1.5]八皇后 Checker Challenge 【经典】

在这里插入图片描述
https://www.luogu.com.cn/problem/P1219

dfs经典的题目,题解不再赘述，记得需要剪枝，不然会超时。

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int a[16];
bool b[16];
int sum=0;
int n;
void dfs(int index)
{
	for(int i=0;i<index;i++)//剪枝
	{
		for(int j=i+1;j<index;j++)
		{
			if(abs(i-j)==abs(a[i]-a[j]))
			{
				return;
			}
		}
	}
	if(index==n)
	{
		sum++;
		if(sum<=3)
		{
			for(int i=0;i<n;i++) cout<<a[i]<<" ";
			cout<<endl;
		}
		return;
	}
	for(int i=1;i<=n;i++)
	{
		if(!b[i])
		{
			a[index]=i;
			b[i]=true;
			dfs(index+1);
			
			b[i]=false;
			a[index]=0;
		}
	}
}
int main(void)
{
	cin>>n;
	dfs(0);	
	cout<<sum<<endl;
	return 0;
}

P1443 马的遍历 【经典bfs】

在这里插入图片描述
https://www.luogu.com.cn/problem/P1443
在这里插入图片描述

经典的BFS模板题：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int n,m;
int startx,starty; 
int dx[8]={-2,-2,2,2,-1,1,-1,1};//8个方向 
int dy[8]={-1,1,-1,1,-2,-2,2,2};//8个方向 
struct node
{
	int x,y,step;//坐标 步长
}Node;
int a[405][405];
bool b[405][405];
void bfs(int x,int y)
{
	Node.x=x;
	Node.y=y;
	Node.step=0;
	a[x][y]=0;
	queue<node>q;
	q.push(Node);
	b[x][y]=true;
	while(!q.empty())	
	{
		node top=q.front();
		q.pop();
		for(int i=0;i<8;i++)
		{
			int tempx=top.x+dx[i];
			int tempy=top.y+dy[i];
			if(tempx>=1&&tempx<=n&&tempy>=1&&tempy<=m&&!b[tempx][tempy]) 
			{
				node temp;
				b[tempx][tempy]=true; 
				temp.x=tempx;
				temp.y=tempy;
				temp.step=top.step+1;
				a[tempx][tempy]=top.step+1;
				q.push(temp);
			}
		}
	}
} 
int main(void)
{
	cin>>n>>m>>startx>>starty;
	bfs(startx,starty);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			//不是起点且还是0，说明是不可达的 
			if(!(i==startx&&j==starty)&&a[i][j]==0) printf("%-5d",-1);
			else printf("%-5d",a[i][j]);
		} 
		cout<<endl;
	}	
	return 0;
}

P2392 kkksc03考前临时抱佛脚 【有意思】

在这里插入图片描述
https://www.luogu.com.cn/problem/P2392
思路：求每一个科目的最短时间。然后相加。
想象有两个队列，判断该数字进入那个队列。
求左右俩队列较小的一个。就是该科目的最小时间。

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int n;
int s[5];
int a[4][25];
int ans=999999999;
int L,R; 
int cnt;
void dfs(int index,int sum)//index当前的个数， sum当前的科目的下标 
{
	 if(index==s[sum])//做完了 
	 {
	 	ans=min(ans,max(L,R));
	 	return;
	 }
	 
	 L+=a[sum][index];//左 
	 dfs(index+1,sum);
	 L-=a[sum][index];//回溯
	 
	 R+=a[sum][index];//右 
	 dfs(index+1,sum);
	 R-=a[sum][index];//回溯
} 
int main(void)
{
	cin>>s[0]>>s[1]>>s[2]>>s[3];
	for(int i=0;i<4;i++)
	{
		for(int j=0;j<s[i];j++)
		{
			cin>>a[i][j];
		}
	} 
	for(int i=0;i<4;i++)
	{
		ans=999999;//初始化 
		L=R=0;//初始化 
		dfs(0,i);
		cnt+=ans;//总的时间 
	} 
	cout<<cnt<<endl;
	return 0;
}

P1135 奇怪的电梯【经典】

在这里插入图片描述
https://www.luogu.com.cn/problem/P1135
按不按的问题，注意点：回溯和剪枝。不剪枝会超时。一定要注意回溯，恢复现场。
唉 ，一个恢复现场让我想了好久。

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=205;
int s[N];
bool ss[N];
int ans=9999999;
int n,a,b; 
int temp;
bool flag=false;
void dfs(int index,int count) //index表示当前所在的楼层  count操作的次数 
{
	if(index==b)
	{
		flag=true;
		ans=min(ans,count);
		return;
	}
	if(count>=ans) return;//剪枝 
	ss[index]=true;
	temp=index+s[index];
	if(temp>=1&&temp<=n&&ss[temp]==false)
	{
		dfs(temp,count+1);//上楼 
	}
	ss[index]=false;
	
	ss[index]=true;
	temp=index-s[index];
	if(temp>=1&&temp<=n&&ss[temp]==false)
	{
		dfs(temp,count+1);//下楼 
	}
	ss[index]=false;//回溯 
}
int main(void)
{
	cin>>n>>a>>b;
	for(int i=1;i<=n;i++) cin>>s[i];
	dfs(a,0);
	if(flag)
		cout<<ans<<endl;
	else
		cout<<-1<<endl;
	return 0;
}

P2895 [USACO08FEB]Meteor Shower S 【有意思 / 秒】

在这里插入图片描述
https://www.luogu.com.cn/problem/P2895

我最早用的是一个朴素的算法: 用一个数组实时的记录看可不可走。
用一个数组把流星可以砸的都赋值。当我们走的时候如果可以走，且所有的流星都没有砸过，说明找到了。
不过这种朴素算法，的时间复杂度和空间复杂度都是十分的长的。最后几个点都TLE了。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
struct star
{
	int x,y,t;
}s[50005];
struct node
{
	int x,y,step;
}Node;
bool hush[305][305];
bool hush1[305][305];//记录所有流星可以砸的
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
bool flag=false;
int n;
int start=0;
bool cmp(star a,star b)
{
	return a.t<b.t;
}
void change(int x, int y)
{
	hush[x][y]=true;
	for(int i=0;i<4;i++)
	{
		int tempx=x+dx[i];
		int tempy=y+dy[i];
		if(tempx>=0&&tempx<=300&&tempy>=0&&tempy<=300)
		hush[tempx][tempy]=true;
	}
}
void change1(int x, int y)
{
	hush1[x][y]=true;
	for(int i=0;i<4;i++)
	{
		int tempx=x+dx[i];
		int tempy=y+dy[i];
		if(tempx>=0&&tempx<=300&&tempy>=0&&tempy<=300)
		hush1[tempx][tempy]=true;
	}
}
void bfs(int x,int y)
{
	for(int i=start;i<n;i++)//第0时刻 
	{
		if(s[i].t==0) 
		change(s[i].x,s[i].y);
		else
		{
			start=i;
			break;
		}
	}
	if(hush[x][y]) return;
	Node.x=x,Node.y=y,Node.step=0;
	hush[x][y]=true;
	queue<node> q; q.push(Node);
	while(!q.empty())
	{
		node top=q.front(); q.pop();
		for(int i=0;i<4;i++) 
		{
			int tempx=top.x+dx[i];
			int tempy=top.y+dy[i];
			int t=top.step+1;
			for(int j=start;j<n;j++)
			{
				if(s[j].t==t) 
				change(s[j].x,s[j].y);
				else
				{
					start=j;
					break;
				}
			}
			if(tempx>=0&&tempx<=300&&tempy>=0&&tempy<=300&&!hush[tempx][tempy])
			{
				node m;
				m.x=tempx,m.y=tempy,m.step=t;
				q.push(m);
				if(!hush1[m.x][m.y])//如果跟我们的流星表比较 看该点是不是所有的流星都打不到
				{
					cout<<m.step<<endl;
					flag=true;
					return;
				} 
			}
		}
	}
}
int main(void)
{
	cin>>n;
	for(int i=0;i<n;i++) scanf("%d%d%d",&s[i].x,&s[i].y,&s[i].t);
	sort(s,s+n,cmp);
	for(int i=0;i<n;i++)
	{
		change1(s[i].x,s[i].y);//初始化将流星可以砸的都赋值
	}
	bfs(0,0);
	if(!flag) cout<<-1<<endl;
	return 0;
}

朴素做法不行，那就优化。 我们可以用一个int 型数组其值就是流星到达的值。 你会发现地图很小，流星很多，
故有很多点流星重复的下落。 对于一个点有多个流星，我们支取最短的时间。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int s[405][405];
int hush[405][405];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
bool flag=false;
struct node
{
	int x,y,step;
}Node;
void change(int x,int y,int t)//将其流星时刻赋值
{
    if(x>=0&&x<=305&&y>=0&&y<=305)
	{
		if(hush[x][y]!=-1) hush[x][y]=min(hush[x][y],t);//如果已经下过了，取时间早的 
		else hush[x][y]=t;
	}
	for(int i=0;i<4;i++)
	{
		int tempx=x+dx[i];
		int tempy=y+dy[i];
		if(tempx>=0&&tempx<=305&&tempy>=0&&tempy<=305)
		{
			if(hush[tempx][tempy]!=-1) hush[tempx][tempy]=min(hush[tempx][tempy],t);//如果已经下过了，取时间早的 
			else hush[tempx][tempy]=t;
		}
	}
}
void bfs(int x,int y)
{
	Node.x=x,Node.y=y,Node.step=0;
	hush[x][y]=0;
	queue<node> q; q.push(Node);
	while(!q.empty())
	{
		node top=q.front(); q.pop();
		for(int i=0;i<4;i++) 
		{
			int tempx=top.x+dx[i];
			int tempy=top.y+dy[i];
			int t=top.step+1;
			if(tempx>=0&&tempx<=305&&tempy>=0&&tempy<=305)
			{
				if(hush[tempx][tempy]==-1)//安全区
				{
					cout<<t<<endl;
					flag=true;
					return;
				}
				if(hush[tempx][tempy]>t) //可以在流星下来之前走
				{
					node m;
					m.x=tempx,m.y=tempy,m.step=t;
					hush[tempx][tempy]=0;
					q.push(m);
				}		
			}
		}
	}
}
int main(void)
{
	int n;cin>>n;
	memset(s,-1,sizeof s);
	memset(hush,-1,sizeof hush);
	for(int i=0;i<n;i++)
	{
		int x,y,t; scanf("%d%d%d",&x,&y,&t);
		if(s[x][y]==-1) //第一次记录
		{
			s[x][y]=t;
			change(x,y,s[x][y]);
			continue;
		}
		if(t<s[x][y]) //取最短的时间
		{
			s[x][y]=min(s[x][y],t);
			change(x,y,s[x][y]);
		}	
	}
	if(hush[0][0]==0)//第一个点0 时间就有流星
	{
		cout<<-1<<endl;
		return 0;
	}
	bfs(0,0);
	if(!flag) cout<<-1<<endl;
	return 0;
}

P1036 [NOIP2002 普及组] 选数 【经典 n中选k】

在这里插入图片描述
https://www.luogu.com.cn/problem/P1036

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=30;
int a[N];
bool b[N];
int n,k;
int ans;
bool judge(int a)
{
	if(a==1) return false;
	if(a==2) return true;
	int temp=sqrt(a);
	for(int i=2;i<=temp;i++)
	{
		if(a%i==0)
			return false;
	}
	return true;
}
void dfs(int start,int sum)
{
	if(sum==k)
	{
		int s=0;
		for(int i=0;i<n;i++)
		{
			if(b[i]) 
			{
				s+=a[i];
			}
		}
		if(judge(s))
			ans++;
		return;
	}
	for(int i=start;i<n;i++)
	{	
	   	if(!b[i]) 
		{
			b[i]=true;
			dfs(i,sum+1);
			b[i]=false;
		}
	}
}
int main(void)
{
	cin>>n>>k;
	for(int i=0;i<n;i++) cin>>a[i];
	dfs(0,0);
	cout<<ans<<endl;
	return 0;
}

P2036 [COCI2008-2009#2] PERKET 【经典】

在这里插入图片描述
https://www.luogu.com.cn/problem/P2036

dfs经典题目，对于每一种都可以选或不选，但是有一个限制条件就是必须要选用哪一个。
所以要排除空的情况。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
int n;
struct node
{
	int a;
	int b;
}Node[15];
bool m[15];
int ans=999999;
void dfs(int index)
{
	if(index==n)
	{
		int sum1=1;
		int sum2=0;
		for(int i=0;i<n;i++)
		{
			if(m[i])
			{
				sum1*=Node[i].a;
				sum2+=Node[i].b;
			}
		}
		int sum=abs(sum1-sum2);
		if(sum2!=0)//至少选了一个
			ans=min(ans,sum);
		return;
	}
	
	m[index]=true;//选
	dfs(index+1);
	
	m[index]=false;不选
	dfs(index+1);
}
int main(void)
{
	cin>>n;
	for(int i=0;i<n;i++) cin>>Node[i].a>>Node[i].b;
	dfs(0);
	cout<<ans;
	return 0;
}

P1605 迷宫 【经典】

在这里插入图片描述
https://www.luogu.com.cn/problem/P1605

经典的dfs解决迷宫的问题，枚举四个方向就可以了。

#include<cstdio>
#include<iostream>
using namespace std;
int m,n,t;
int x,y,xx,yy;
int a[10][10];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int ans; 
void dfs(int x,int y)
{
	if(x==xx&&y==yy)
	{
		ans++;
		return;
	}
	a[x][y]=-1;
	for(int i=0;i<4;i++)
	{
		int tempx=x+dx[i];
		int tempy=y+dy[i];
		if(tempx>=1&&tempx<=n&&tempy>=1&&tempy<=m&&a[tempx][tempy]!=-1)
		{
			a[tempx][tempy]=-1;
			dfs(tempx,tempy);
			a[tempx][tempy]=0;
		}
	}
}
int main(void)
{
	cin>>m>>n>>t;
	cin>>x>>y>>xx>>yy;
	for(int i=0;i<t;i++)
	{
		int tx,ty;
		cin>>tx>>ty;
		a[tx][ty]=-1;
	}
	dfs(x,y);
	cout<<ans<<endl;
	return 0; 
}

P1101 单词方阵 【有意思】

在这里插入图片描述
https://www.luogu.com.cn/problem/P1101
这道题挺有意思的，它是有8个方向，不过它有一个特点。
就是方向是笔直的一直走，不像传统的迷宫4个方向遍历走。
它是当方向正确后，朝着一个方向一直走。看符不符合条件就行了。
在这里插入图片描述

#include<iostream>
#include<string>

using namespace std;

const int N=105;

int n;
char a[N][N];//保存数组 
char ans[N][N];//结果数组 
int dx[8]={-1,-1,-1,0,0,1,1,1};//8个方向 
int dy[8]={-1,0,1,-1,1,-1,0,1};
string cmp="yizhong";//比较字符串 

void dfs(int x,int y)
{
	for(int i=0;i<8;i++)//8个方向挨个的遍历 
	{
		int tempx=x+dx[i];
		int tempy=y+dy[i];
		bool flag=false;
		if(tempx>=0&&tempx<n&&tempy>=0&&tempy<n)//坐标合法 
		{
			for(int j=1;j<=6;j++)//以该方向走六步，看是不是izhong 
			{
				int cmpx=x+j*dx[i];
				int cmpy=y+j*dy[i];
				if( !(cmpx>=0&&cmpx<n&&cmpy>=0&&cmpy<n)) break;//坐标不合法 
				if( a[cmpx][cmpy]!=cmp[j]) break;//不匹配 
				if(j==6)//说明完全匹配 
					flag=true;		
			}
		}
		if(flag)//保存结果 
		{
			for(int j=0;j<=7;j++)
			{
				int cmpx=x+j*dx[i];
				int cmpy=y+j*dy[i];
				ans[cmpx][cmpy]=cmp[j];
			}
		}	
	}
}
int main(void)
{
	cin>>n;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			cin>>a[i][j];
	
	for(int i=0;i<n;i++)//dfs遍历 
		for(int j=0;j<n;j++)
		{
			if(a[i][j]=='y') 
			{
				dfs(i,j);
			}
		}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			if(!ans[i][j]) cout<<"*";//0的话输出* 
			else cout<<ans[i][j];
		}
		cout<<endl;	
	}	
	return 0;	
}

P2404 自然数的拆分问题 【有点意思 / 经典】

在这里插入图片描述
https://www.luogu.com.cn/problem/P2404

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n;
int a[20];
void print(int next)
{
	for(int i=0;i<next;i++)
	{
		if(i==0) cout<<a[i];
		else cout<<"+"<<a[i];
	}
	cout<<endl;
}
void dfs(int start,int sum,int index)//从哪个数开始  当前的总的和  当前的坐标 
{
	if(start==n) return;
	
	if(sum==n) 
	{
		print(index);
		return;
	}
	
	for(int i=start;i<=n-sum;i++)//这里让其从小到大，避免了重复
	{
		a[index]=i;
		dfs(i,sum+i,index+1);
		a[index]=0;
	}
}
int main(void)
{
	cin>>n;
	dfs(1,0,0);
	return 0;	
}

P1596 [USACO10OCT]Lake Counting S 【经典】

在这里插入图片描述
https://www.luogu.com.cn/problem/P1596
连通块问题，找到一个符合条件的起点 用dfs枚举的走一遍。走的同时将其复位，如本题"W" 走过后复位为0.
那么经过该次的操作后，这个连通块就都复位了。统计dfs()的次数就可以了。
类似于一个清理大队，将周围可以到达的地方都清理干净。

#include<cstdio>
#include<iostream>
using namespace std;
const int N=105;
char a[N][N];
int n,m;
int sum;
int dx[8]={-1,-1,-1,0,0,1,1,1};
int dy[8]={-1,0,1,-1,1,-1,0,1};
void dfs(int x,int y)
{
	a[x][y]='0';//恢复
	for(int i=0;i<8;i++)
	{
		int tempx=x+dx[i];
		int tempy=y+dy[i];
		if(tempx>=0&&tempx<n&&tempy>=0&&tempy<m&&a[tempx][tempy]=='W')
		{
			dfs(tempx,tempy);
		}
	}
}
int main(void)
{
	cin>>n>>m;
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			cin>>a[i][j];
	
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			if(a[i][j]=='W')
			{
				dfs(i,j);
				sum++;
			}
		}
	}
	cout<<sum<<endl;
	return 0;
}

P1162 填涂颜色 【思维秒】

在这里插入图片描述
https://www.luogu.com.cn/problem/P1162
因为只有一个闭环。故边缘处一定有零，或者没有零外面一圈的1。
只要把矩阵边缘都搜一下。把边缘的0都变成 3…输出的时候再变回来。
注意的一点: 是再搜的时候我们要看当前是不是1 是1的话就不搜，0再搜。

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
const int N=35;
int a[N][N];
int n;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
void dfs(int x,int y)
{
	if(a[x][y]==0)//起点
		a[x][y]=3;
	else
		return;
	for(int i=0;i<4;i++)
	{
		int tempx=x+dx[i];
		int tempy=y+dy[i];
		if(tempx>=0&&tempx<n&&tempy>=0&&tempy<n&&a[tempx][tempy]==0)
		{
			dfs(tempx,tempy);
		}
	}
}
int main(void)
{
	cin>>n;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			cin>>a[i][j];
	for(int i=0;i<n;i++)//行 
		dfs(0,i);
	for(int i=0;i<n;i++)//列 
		dfs(i,0);
	for(int i=0;i<n;i++)//最后一行 
		dfs(n-1,i);	
	for(int i=0;i<n;i++)//最后一列 
		dfs(i,n-1);	
		
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			if(a[i][j]==3) 
				cout<<0<<" "; 
			if(a[i][j]==0)
				cout<<2<<" ";
			if(a[i][j]==1) 
			cout<<a[i][j]<<" ";
		}
		cout<<endl;
	}
	return 0;
}

P1032 [NOIP2002 提高组] 字串变换 【bfs 字符串】

在这里插入图片描述
https://www.luogu.com.cn/problem/P1032

注意：这里有一个坑就是同一个字符串变换的规则可能有多个。
例:
abc 123
abc 456
abc既可以变成123也可以变成456。
我最开始用的map来映射结果发现不对，最后还是用来数组一 一对应映射。

#include<cstdio>
#include<iostream>
#include<string>
#include<map>
#include<queue>
#include<set>
using namespace std;

string a1[7];//变换规则 
string a2[7];//变换规则 
int w;//规则个数 
map<string,bool>vis;//去重 避免反复变换 
string s,ans;// 初始状态 和 目标状态 

struct node
{
	string s;
	int step;
}Node;
bool flag=false;
void bfs(string a)
{
	Node.s=a ,Node.step=0;
	queue<node>q; vis[a]=true;
	q.push(Node);
	while(!q.empty())
	{
		node top=q.front();
		if(top.step>=10) 
		{
			cout<<"NO ANSWER!"<<endl;
			return;
		}
		q.pop();
		for(int i=0;i<w;i++)//枚举每种的变换规则
		{
			string t=top.s;
			string temp=a1[i];
			for(int z=0;z<t.size();z++)//从字符串中找看有没有可以变换的 
			{
				if(t[z]==temp[0])//开头匹配 
				{
					int startx=z;//记录开头匹配的下标 
					int endx=0;// 记录结束匹配的下标 
					int j=z;
					int k=0;
					while(t[j]==temp[k]&&k<temp.size())
					{
						j++,k++;
					} 
					endx=j;
					if(k==temp.size())//说明完全匹配，可以变换 
					{
						string ss=top.s.substr(0,startx);
						ss+=a2[i];//将其替换 
						ss+=top.s.substr(endx,top.s.size()-endx);
						if(!vis[ss]) 
						{
							vis[ss]=true;
							node m;
							m.s=ss,m.step=top.step+1;
							if(m.s==ans)
							{
							    flag=true;
								if(m.step>=10) cout<<"NO ANSWER!"<<endl;
								else cout<<m.step<<endl;
								return;
							}
							q.push(m);
						}
					}
				}
			}
		}
	}
}
int main(void)
{
	cin>>s>>ans;
	while(cin>>a1[w]>>a2[w]) w++;
	bfs(s);
	if(!flag) cout<<"NO ANSWER!"<<endl;
	return 0;
}

后来发现直接用: replace函数它不香吗?

#include<cstdio>
#include<iostream>
#include<string>
#include<map>
#include<queue>
#include<set>
using namespace std;

string a1[7];//变换规则 
string a2[7];//变换规则 
int w;//规则个数 
map<string,bool>vis;//去重 避免反复变换 
string s,ans;// 初始状态 和 目标状态 

struct node
{
	string s;
	int step;
}Node;
bool flag=false;
void bfs(string a)
{
	Node.s=a ,Node.step=0;
	queue<node>q; vis[a]=true;
	q.push(Node);
	while(!q.empty())
	{
		node top=q.front();
		if(top.step>=10) 
		{
			cout<<"NO ANSWER!"<<endl;
			return;
		}
		q.pop();
		for(int i=0;i<w;i++)//枚举每种的变换规则
		{
			string t=top.s;
			string temp=a1[i];
			for(int z=0;z<t.size();z++)//从字符串中找看有没有可以变换的 
			{
				if(t[z]==temp[0])//开头匹配 
				{
					int startx=z;//记录开头匹配的下标 
					int j=z;
					int k=0;
					while(t[j]==temp[k]&&k<temp.size())
					{
						j++,k++;
					} 
					if(k==temp.size())//说明完全匹配，可以变换 
					{
						string ss=top.s;
						ss.replace(startx,temp.size(),a2[i]);
						if(!vis[ss]) 
						{
							vis[ss]=true;
							node m;
							m.s=ss,m.step=top.step+1;
							if(m.s==ans)
							{
							    flag=true;
								if(m.step>=10) cout<<"NO ANSWER!"<<endl;
								else cout<<m.step<<endl;
								return;
							}
							q.push(m);
						}
					}
				}
			}
		}
	}
}
int main(void)
{
	cin>>s>>ans;
	while(cin>>a1[w]>>a2[w]) w++;
	bfs(s);
	if(!flag) cout<<"NO ANSWER!"<<endl;
	return 0;
}

P1825 [USACO11OPEN]Corn Maze S 【有意思 传送门】

在这里插入图片描述
https://www.luogu.com.cn/problem/P1825
注意的点：

###=###
#.....#
###A###
#.....#
#@#####
###a..#
#######
a,A一对传送门。 要先进入A从a出来，再进人a从A出来，不然不可以到终点，a就是一个中转站。

所以传送门不要标记

还要注意有的传送门是一个点，这时他其实和普通的点没有不同。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<string>
using namespace std;

bool vis[305][305];
string a[305];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int n,m;
int startx,starty,endx,endy;
struct node
{
	int x,y,step;
}Node;
void bfs(int x,int y)
{
	Node.x=x,Node.y=y,Node.step=0;
	queue<node> q; q.push(Node);
	vis[x][y]=true;
	while(!q.empty())
	{
		node top=q.front(); q.pop();
		if(top.x==endx&&top.y==endy)
		{
			cout<<top.step<<endl;
			return ;
		}
		for(int i=0;i<4;i++)
		{
			int tempx=top.x+dx[i];
			int tempy=top.y+dy[i];
			if(tempx<0||tempx>=n||tempy<0||tempy>=m) continue;//越界 
			if(vis[tempx][tempy]) continue;//走过了 
			if(a[tempx][tempy]=='#') continue;//墙 
			bool flag=false;
			if(a[tempx][tempy]>='A'&&a[tempx][tempy]<='Z')
			{
				for(int j=0;j<n;j++)
				{
					for(int k=0;k<m;k++)
					{
						if(a[j][k]==a[tempx][tempy]&&(j!=tempx||k!=tempy))//找到了对应的传送门
						{
							flag=true;
							node m;
							m.x=j,m.y=k,m.step=top.step+1;
							q.push(m);
						}
					}
				}
			}
			if(!flag)
			{
				node m;
				m.x=tempx,m.y=tempy,m.step=top.step+1;
				vis[m.x][m.y]=true;
				q.push(m);
			}
		}
	}
}
int main(void)
{
	cin>>n>>m;
	for(int i=0;i<n;i++) cin>>a[i];
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			if(a[i][j]=='@') startx=i,starty=j;
			if(a[i][j]=='=') endx=i,endy=j;
		}
	}
	bfs(startx,starty);
	return 0;
}