宽搜错题小仓库
宽搜 最短路：
基础： 回家最短距离
提高：
逃离地牢（三维）
如何替换结构体：
q[tt++]=x*(n+1)+y;
px=p/(n+1);
py=p%(n+1);dis数组替换vis数组： 开头用
memset(dis,-1,sizeof(dis));//将dis数组全部设为-1之后，dis数组中不为-1的就是没遍历过的。
多源dfs： 躲避漏水的卡皮巴拉 plus
#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
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开始连通块
#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分）：
#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代码：
#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数组和以往不一样，它记录的是经过它的最大血量
#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;
}