河西S班广搜测试 - 洛谷保存站

# T1[USACO19OPEN] Bucket Brigade B
将石块看成障碍物，湖看成起点，牛棚看成终点，跑一遍$BFS$找出起点到终点的最短路

```cpp
#include<bits/stdc++.h>
using namespace std;
struct node{
	int x,y,step;
};
queue<node>q;
char mp[15][15];
int dx[10]={1,0,-1,0};
int dy[10]={0,1,0,-1};
int vis[15][15],tx,ty;
int main(){
	for(int i=1;i<=10;i++)
		for(int j=1;j<=10;j++)
			cin>>mp[i][j];
	for(int i=1;i<=10;i++)
		for(int j=1;j<=10;j++)	
			if(mp[i][j]=='L'){
				vis[i][j]==1;
				q.push({i,j,0});
			}else if(mp[i][j]=='B')tx=i,ty=j;
	while(!q.empty()){
		node t=q.front();
		q.pop();
		if(t.x==tx&&t.y==ty){
			cout<<t.step-1<<"\n";
			return 0;
		}
		for(int i=0;i<4;i++){
			int nx=dx[i]+t.x,ny=dy[i]+t.y;
			if(nx<1||nx>10||ny<1||ny>10)continue;
			if(vis[nx][ny]==1||mp[nx][ny]=='R')continue;
			vis[nx][ny]=1;
			q.push({nx,ny,t.step+1});
		}
	}
	return 0;
}
```
# T2 P1443 马的遍历
> 马走日，象走田

一道变种的$BFS$

将模板的东南西北四个方向换成**日**字形的$8$个方向再进行搜索，每到达一个地方就将它标注时间，这样就只用跑一遍$BFS$了

```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=405;
int n,m,sx,sy;
struct node{
	int x,y,step;
};
queue<node>q;
int mp[N][N];
int dx[10]={1,2,-1,2,-2,-2,1,-1};
int dy[10]={2,1,2,-1,1,-1,-2,-2};
bool vis[N][N];
int main(){
	memset(mp,-1,sizeof mp);
	cin>>n>>m>>sx>>sy;
	vis[sx][sy]=1;
	mp[sx][sy]=0;
	q.push({sx,sy,0});
	while(!q.empty()){
		node t=q.front();
		q.pop();
		for(int i=0;i<8;i++){
			int nx=dx[i]+t.x,ny=dy[i]+t.y;
			if(nx<1||nx>n||ny<1||ny>m)continue;
			if(vis[nx][ny]==1)continue;
			vis[nx][ny]=1;
			q.push({nx,ny,t.step+1});
			mp[nx][ny]=t.step+1;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++)
			cout<<mp[i][j]<<" ";
		cout<<"\n"; 
	}
	return 0;
}
```
# T3 [USACO10OCT] Lake Counting S

判连通块的模板题

每次发现水洼且未到过，就用**搜索**将次连通块标记为到过

```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n,m,ans=0;
struct node{
	int x,y;
};
queue<node>q;
char mp[N][N];
int dx[10]={1,-1,-1,1,0,0,-1,1};
int dy[10]={1,1,-1,-1,-1,1,0,0};
bool vis[N][N];
void bfs(){
	while(!q.empty()){
		node t=q.front();
		q.pop();
		for(int i=0;i<8;i++){
			int nx=dx[i]+t.x,ny=dy[i]+t.y;
			if(nx<1||nx>n||ny<1||ny>m)continue;
			if(vis[nx][ny]==1||mp[nx][ny]=='.')continue;
			vis[nx][ny]=1;
			q.push({nx,ny});
		}
	}
	return;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>mp[i][j];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			if(vis[i][j]==0&&mp[i][j]=='W'){
				ans++;
				q.push({i,j});
				vis[i][j]=1;
				bfs();
			}
		}
	cout<<ans;
	return 0;
}
```

# T4 Catch That Cow S

**抓住那头牛！！！**

一道**一维广搜**

每次搜索$-1,+1,*2$即可

```cpp
#include<bits/stdc++.h>
using namespace std;
int T;
int sx,tx;
struct node{
	int x,step;
};
queue<node>q;
const int N=2e6+5;
bool vis[N];
int bfs(){
	while(!q.empty()){
		node t=q.front();
		q.pop();
		if(t.x==tx){
			return t.step;
		}
		for(int i=1;i<=3;i++){
			int nx;
			if(i==1)nx=t.x-1;
			if(i==2)nx=t.x+1;
			if(i==3)nx=t.x*2;
			if(nx<0||nx>N)continue;
			if(vis[nx]==1)continue;
			vis[nx]=1;
			q.push({nx,t.step+1});
		} 
	}
}
int main(){
	cin>>T;
	while(T--){
		memset(vis,0,sizeof vis);
		while(!q.empty())q.pop();
		cin>>sx>>tx;
		q.push({sx,0});
		cout<<bfs()<<"\n";
	}
	return 0;
}
```

# T5 Cows on Skates G

妥妥的$BFS$

但是它和模板**不一样**，它只用**输出路径**

（这样的路径可能有无数种，只用输出任意一种，~~样例十分银杏只有一种~~）

那该如何**输出路径**呢，用一个$pre$数组来存下每个节点的上一个节点，最后从终点倒着遍历到起点一路用栈存下来，最后就可以输出路径了

~~很像并查集~~
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=155;
int n,m,ans;
struct node{
	int x,y;
};
node pre[N][N];
queue<node>q;
char mp[N][N];
int dx[10]={0,0,-1,1};
int dy[10]={-1,1,0,0};
bool vis[N][N];
void bfs(){
	while(!q.empty()){
		node t=q.front();
		if(t.x==n&&t.y==m)return;
		q.pop();
		for(int i=0;i<4;i++){
			int nx=dx[i]+t.x,ny=dy[i]+t.y;
			if(nx<1||nx>n||ny<1||ny>m)continue;
			if(vis[nx][ny]==1||mp[nx][ny]=='*')continue;
			vis[nx][ny]=1;
			q.push({nx,ny});
			pre[nx][ny]=t;
		}
	}
	return;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>mp[i][j];
	vis[1][1]=1;
	q.push({1,1});
	bfs();
	vector<node>v;
	int x=n,y=m,tmpx,tmpy;
	while(1){
		v.push_back({x,y});
		tmpx=pre[x][y].x,tmpy=pre[x][y].y;
		x=tmpx,y=tmpy;
		if(x==1&&y==1)break;
	}
	v.push_back({1,1});
	for(int i=v.size()-1;i>=0;i--)cout<<v[i].x<<" "<<v[i].y<<"\n";
	return 0;
}
```

# T6 血色先锋队

一道的**洪水填充**题目的变种

填充的是此节点被感染的时间

最后他问哪里你就答哪里就好了

```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,a,b;
const int N=505;
struct node{
	int x,y,step;
};
queue<node>q;
int mp[N][N];
int dx[10]={0,0,-1,1};
int dy[10]={-1,1,0,0};
bool vis[N][N];
int main(){
	memset(mp,0x3f,sizeof mp);
	cin>>n>>m>>a>>b;
	while(a--){
		int x,y;
		cin>>x>>y;
		q.push({x,y,0});
		vis[x][y]=1;
		mp[x][y]=0;
	}
	while(!q.empty()){
		node t=q.front();
		q.pop();
		for(int i=0;i<4;i++){
			int nx=dx[i]+t.x,ny=dy[i]+t.y;
			if(nx<1||nx>n||ny<1||ny>m)continue;
			if(vis[nx][ny]==1)continue;
			vis[nx][ny]=1;
			mp[nx][ny]=t.step+1;
			q.push({nx,ny,t.step+1});
		}
	}
	while(b--){
		int x,y;
		cin>>x>>y;
		cout<<mp[x][y]<<"\n";
	}
	return 0;
}
```

# T7回家

用**原来的搜索**模拟小H的路线

只需在结构体里增加一个血量$hp$，当$hp==0$时，自然就隔了

可惜只有$84pts$

```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,sx,sy,tx,ty;
int mp[15][15];
int dx[10]={0,0,-1,1};
int dy[10]={-1,1,0,0};
bool vis[15][15];
struct node{
	int x,y,step,xue;
};
queue<node>q;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++) 
			cin>>mp[i][j];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(mp[i][j]==2)sx=i,sy=j;
			else if(mp[i][j]==3)tx=i,ty=j;
	q.push({sx,sy,0,6});
	vis[sx][sy]=1;
	while(!q.empty()){
		node t=q.front();
		q.pop();
		if(t.x==tx&&t.y==ty){
			cout<<t.step<<"\n";
			return 0;
		}
		for(int i=0;i<4;i++){
			int nx=dx[i]+t.x,ny=dy[i]+t.y;
			if(nx<1||nx>n||ny<1||ny>m)continue;
			if(vis[nx][ny]==1||mp[nx][ny]==0)continue;
			if(t.xue-1==0)continue;
			if(mp[nx][ny]==4)q.push({nx,ny,t.step+1,t.xue});
			else q.push({nx,ny,t.step+1,t.xue-1});
		}
	}
	cout<<-1;
	return 0;
}
```

很快我们就可以发现错误

如果样例是这样的：

|2|0|0|
|:-:|:-:|:-:|
|1|0|0|
|1|4|0|
|1|0|0|
|1|1|3|

这道题大家很快就可以发现

按照常规思路我们沿着左下的边一路走

就会在家门口死去

那为了**续命**（~~生命高于一切~~）我们只能在$(1,3)$是右转去领取鼠标

这时候，你会惊奇的发现你回不来了，因为的唯一的出路已经被$vis$数组给堵上了

所以我们要将$vis$弄成三维的，第三维用来存血量$hp$

$100pts!$

```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,sx,sy,tx,ty;
int mp[15][15];
int dx[10]={0,0,-1,1};
int dy[10]={-1,1,0,0};
bool vis[105][105][105];
struct node{
	int x,y,step,hp;
};
queue<node>q;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++) 
			cin>>mp[i][j];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(mp[i][j]==2)sx=i,sy=j;
			else if(mp[i][j]==3)tx=i,ty=j;
	q.push({sx,sy,0,6});
	vis[sx][sy][6]=1;
	while(!q.empty()){
		node t=q.front();
		q.pop();
		if(t.x==tx&&t.y==ty){
			cout<<t.step<<"\n";
			return 0;
		}
		for(int i=0;i<4;i++){
			int nx=dx[i]+t.x;
			int ny=dy[i]+t.y;
			if(nx<1||ny<1||nx>n||ny>m)continue;
			if(vis[nx][ny][t.hp]==1)continue;
			if(mp[nx][ny]==0)continue;
			if(t.hp-1<=0)continue;
			vis[nx][ny][t.hp]=1;
			if(mp[nx][ny]==4)q.push({nx,ny,t.step+1,6});
			else q.push({nx,ny,t.step+1,t.hp-1});
		}
	}
	cout<<-1;
	return 0;
}
```
# T8 魔板 Magic Squares

个人认为与T4类似都是3种情况：$A、B、C$

但还是有**亿**点点不同

- 需要输出操作序列
- 如何判重

解决方案：

- 笨办法，在结构体中多加一个字符串存下操作序列
- 用$map<>定义vis$判重

```cpp
#include<bits/stdc++.h>
using namespace std;
string ans="";
struct node{
	int step;
	string x,pre;
};
queue<node>q;
map<string,bool>vis;
string A(string x){
	for(int i=0;i<4;i++)swap(x[i],x[7-i]);
	return x;
}
string B(string x){
	string tmp="";
	tmp+=x[3];
	for(int i=0;i<3;i++)tmp+=x[i];
	for(int i=5;i<8;i++)tmp+=x[i];
	tmp+=x[4];
	return tmp;
}
string C(string x){
	char tmp=x[1];
	x[1]=x[6],x[6]=x[5],x[5]=x[2],x[2]=tmp;
	return x;
}
int main(){
	q.push({0,"12345678",""});
	vis["12345678"]=1;
	for(int i=0;i<8;i++){
		char c;
		cin>>c;
		ans+=c;
	}
	while(!q.empty()){
		node t=q.front();
		q.pop();
		if(t.x==ans){
			cout<<t.step<<"\n";
			cout<<t.pre<<"\n";
			return 0;
		}
		for(int i=1;i<=3;i++){
			string nx,np;
			if(i==1)nx=A(t.x),np=t.pre+"A";
			if(i==2)nx=B(t.x),np=t.pre+"B";
			if(i==3)nx=C(t.x),np=t.pre+"C";
			if(vis[nx]==1)continue;
			vis[nx]=1;
			q.push({t.step+1,nx,np});
		}
	}
	return 0;
}
```

正在渲染内容...