专栏文章

宽搜错题小仓库

jjcs_pp
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqpffrx
此快照首次捕获于
2025/12/04 08:35
3 个月前
此快照最后确认于
2025/12/04 08:35
3 个月前
查看原文

宽搜 最短路：

基础： 回家最短距离
提高：
逃离地牢（三维）
如何替换结构体：
CPP
q[tt++]=x*(n+1)+y;
px=p/(n+1);
py=p%(n+1);
dis数组替换vis数组： 开头用
CPP
memset(dis,-1,sizeof(dis));//将dis数组全部设为-1
之后，dis数组中不为-1的就是没遍历过的。
多源dfs： 躲避漏水的卡皮巴拉 plus
CPP
#include <bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m;
char a[N][N];
int hh,tt,q[N*N];
int d[N][N],dx[]={-1,0,1,0},dy[]={0,-1,0,1};
int xx[N],yy[N],cnt=1;
void f()
{
	for(int i=1;i<cnt;i++)
	{
		q[tt++]=xx[i]*(n+1)+yy[i];
		d[xx[i]][yy[i]]=0;
	}
	while(hh<tt)
	{
		int p=q[hh++];
		int px=p/(n+1);
		int py=p%(n+1);
		for(int i=0;i<4;i++)
		{
			int nx=px+dx[i];
			int ny=py+dy[i];
			if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&d[nx][ny]==-1&&a[nx][ny]!='#')
			{
				q[tt++]=nx*(n+1)+ny;
				d[nx][ny]=d[px][py]+1;
			}
		}
	}
}
int main(){
	memset(d,-1,sizeof(d));
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>a[i][j];
			if(a[i][j]=='*')
			{
				xx[cnt]=i;
				yy[cnt++]=j;
			}
		}
	}
	f();
	int qx,qy;
	for(int i=1;i<=m;i++)
	{
		cin>>qx>>qy;
		if(a[qx][qy]=='#') cout<<'#';
		else if(d[qx][qy]==-1) cout<<"safe";
		else cout<<d[qx][qy];
		cout<<'\n';
	}
    return 0;
}

连通块

基础：求糖果数量
进阶：填数字
方法：在外面补一圈0
CPP
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 1 1 1 1 0
0 0 1 1 0 0 1 0
0 1 1 0 0 0 1 0
0 1 0 0 0 0 1 0
0 1 1 1 1 1 1 0
0 0 0 0 0 0 0 0
然后从0，0开始连通块
CPP
#include <bits/stdc++.h>
using namespace std;
const int N=110;
int n;
int a[N][N];
int v[N][N],dx[]={-1,0,1,0},dy[]={0,-1,0,1};
int q[N*N],hh,tt;
void f(int x,int y)
{
	q[tt++]=x*N+y;
	v[x][y]=1;
	while(hh<tt)
	{
		int p=q[hh++],px=p/N,py=p%N;
		for(int i=0;i<4;i++)
		{
			int nx=px+dx[i],ny=py+dy[i];
			if(nx<=n+1&&nx>=0&&ny<=n+1&&ny>=0&&v[nx][ny]==0&&a[nx][ny]==0)//补0后边界扩大
			{
				v[nx][ny]=1;
				q[tt++]=nx*N+ny;
			}
		}
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			cin>>a[i][j];
	f(0,0);//补0后从0开始
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(a[i][j]==1) cout<<"1 ";
			else if(v[i][j]==0) cout<<"2 ";
			else cout<<"0 ";
		}
		cout<<'\n';
	}
}

P8673 [蓝桥杯 2018 国 C] 迷宫与陷阱

迷宫与陷阱

基本思路：

队列用结构体：位置x,y,无敌时间time1，时间time2
如果吃到了无敌道具，将time1设为k,之后每步-1
一版代码（90分）：
CPP
#include <bits/stdc++.h>
using namespace std;
const int N=2010;
struct ST{
	int x,y;
	int time;//无敌时间 
	int time2;//时间 
}q[N*N];
int n,k,hh,tt;
char a[N][N];
int v[N][N],dx[]={1,0,-1,0},dy[]={0,1,0,-1},flag=1;
void f(){
	while(hh<tt)
	{
		int px=q[hh].x,py=q[hh].y,t1=q[hh].time,t2=q[hh++].time2;
//		printf("\nout %d %d %d %d\n",px,py,t1,t2);
		if(px==n&&py==n)
		{
			cout<<t2;
			flag=0;
			return;
		}
		for(int i=0;i<4;i++)
		{
			int nx=px+dx[i],ny=py+dy[i];
			if(nx<=n&&nx>0&&ny<=n&&ny>0&&a[nx][ny]!='#'&&(a[nx][ny]!='X'||t1>0)&&(v[nx][ny]==0||v[nx][ny]<4&&t1>0))
			{
				q[tt].x=nx;q[tt].y=ny;q[tt].time=t1-1;q[tt].time2=t2+1;
				if(a[nx][ny]=='%')
				{
					q[tt].time=k;
					a[nx][ny]='.';
				}
				tt++;
				v[nx][ny]++;
//				printf("in  %d %d %d %d\n",nx,ny,q[tt-1].time,t2+1);
			}
		}
	}
}
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>a[i][j];
		}
	}
	q[tt].x=1;
	q[tt++].y=1;
	v[1][1]++;
	f();
	if(flag) cout<<-1;
}
//左上角(1,1)->右下角(n,n)
//上下左右
//.可以经过，#不能经过，X有陷阱，%有无敌道具
难点：
一个点可能被经过不止4次
AK代码：
CPP
#include <bits/stdc++.h>
using namespace std;
const int N=2010;
struct ST{
	int x,y;
	int time;//无敌时间 
	int time2;//时间 
}q[N*N];
int n,k,hh,tt;
char a[N][N];
int v[N][N],dx[]={1,0,-1,0},dy[]={0,1,0,-1},flag=1;
void f(){
	while(hh<tt)
	{
		int px=q[hh].x,py=q[hh].y,t1=q[hh].time,t2=q[hh++].time2;
//		printf("\nout %d %d %d %d\n",px,py,t1,t2);
		if(px==n&&py==n)
		{
			cout<<t2;
			flag=0;
			return;
		}
		for(int i=0;i<4;i++)
		{
			int nx=px+dx[i],ny=py+dy[i];
			if(nx<=n&&nx>0&&ny<=n&&ny>0&&a[nx][ny]!='#'&&(a[nx][ny]!='X'||t1>0)&&(v[nx][ny]==0||v[nx][ny]<10&&t1>0))//这里改了，将4改成了10
			{
				q[tt].x=nx;q[tt].y=ny;q[tt].time=t1-1;q[tt].time2=t2+1;
				if(a[nx][ny]=='%')
				{
					q[tt].time=k;
					a[nx][ny]='.';
				}
				tt++;
				v[nx][ny]++;
//				printf("in  %d %d %d %d\n",nx,ny,q[tt-1].time,t2+1);
			}
		}
	}
}
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>a[i][j];
		}
	}
	q[tt].x=1;
	q[tt++].y=1;
	v[1][1]++;
	f();
	if(flag) cout<<-1;
}
//左上角(1,1)->右下角(n,n)
//上下左右
//.可以经过，#不能经过，X有陷阱，%有无敌道具

P2802 回家

基本思路：

v数组和以往不一样，它记录的是经过它的最大血量
CPP
#include <bits/stdc++.h>
using namespace std;
int n,m,a[11][11];
struct ST
{
	int x,y;//位置 
	int xh,step;//血量，步数 
}q[100010];
int v[11][11],dx[]={-1,0,1,0},dy[]={0,-1,0,1};
int hh,tt;
void f()
{
	while(hh<tt)
	{
		ST p=q[hh++];
		int px=p.x,py=p.y;
		if(p.xh==0) continue;//血量没了，小H out 
		if(a[px][py]==4)//捡到鼠标，血量回满！小H满血复活！！！ 
		{
			p.xh=6;
			v[px][py]=6;
		}
		if(a[px][py]==3)//到家啦~~ 
		{
			cout<<p.step;
			return;
		}
		for(int i=0;i<4;i++)
		{
			int nx=px+dx[i],ny=py+dy[i];
			if(nx>0&&nx<=n&&ny>0&&ny<=m&&v[nx][ny]<p.xh&&a[nx][ny]!=0)
			{
				v[nx][ny]=p.xh;
				q[tt++]={nx,ny,p.xh-1,p.step+1};
			}
		}
	}
	cout<<-1;//函数没return，说明小H没到家：安息吧，小H！ 
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];
			if(a[i][j]==2)//找到起点，入队 
			{
				q[tt++]={i,j,6,0};
				v[i][j]=6;
			}
		}
	}
	f();
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...