DFS(深搜)
之前写过三篇关于dfs的
练习总结:
基础算法--递归搜索DFS练习总结(上)-CSDN博客
基础算法--递归搜索DFS练习总结(中)-CSDN博客
基础算法--递归搜索DFS练习总结(下)-CSDN博客
以下题目均为
补充练习:
P1460 [USACO2.1] 健康的荷斯坦奶牛 Healthy Holsteins
第一种暴力搜索dfs(超时未AC 90 points):
#include<iostream>
#include<cstring>
using namespace std;
int n,m,a[30],b[20][30],c[30],ans;
bool flag[20],key;
bool check(){for(int i=1;i<=n;i++){for(int j=1;j<=m;j++) if(flag[j]) c[i]+=b[j][i];if(a[i]>c[i]) return false;}return true;
}
void dfs(int x,int cnt){if(x==cnt+1){if(check()) {key=true;ans=cnt;}memset(c,0,sizeof c);return ;}for(int i=x;i<=m;i++){if(!flag[i]){flag[i]=true;dfs(x+1,cnt);if(key) return ;flag[i]=false;}}
}
int main(){cin>>n;for(int i=1;i<=n;i++) cin>>a[i];cin>>m;for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) cin>>b[i][j];for(int i=1;i<=m;i++){memset(flag,0,sizeof flag);memset(c,0,sizeof c);dfs(1,i);if(key){cout<<ans<<" ";for(int i=1;i<=m;i++) if(flag[i]) cout<<i<<" ";return 0;}}
}第二种暴力搜索dfs(AC):
#include<iostream>
using namespace std;
int n,m,a[30],b[20][30],c[30],ans=1e9,res[30];
//数组c:每次搜索选的饲料编号,数组res:存储解
//判断每次选的那些饲料中的维生素之和是不是都大于等于牛需要的量
bool check(int x){for(int i=1;i<=n;i++){int sum=0;for(int j=1;j<=x;j++) sum+=b[c[j]][i];if(sum<a[i]) return false;}return true;
}
void dfs(int curPos,int curCnt){if(curPos>m){//当前位置超过边界if(check(curCnt)){//必须使牛够吃if(curCnt<ans){//如果小于以前的最优解ans=curCnt;//更新答案for(int i=1;i<=m;i++) res[i]=c[i];//更新答案数组}}return ;}c[curCnt+1]=curPos;//把当前位置放在数组里dfs(curPos+1,curCnt+1);//搜索一步c[curCnt+1]=0;//回溯一步dfs(curPos+1,curCnt);//如果不选第curPos种饲料
}
int main(){cin>>n;for(int i=1;i<=n;i++) cin>>a[i];cin>>m;for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) cin>>b[i][j];dfs(1,0);cout<<ans<<" ";for(int i=1;i<=ans;i++) cout<<res[i]<<" ";return 0;
}P1451 求细胞数量
dfs(AC):
思路:不为0的地方就是细胞,然后dfs搜连通块,把搜到的都归0,保证不重复
#include<iostream>
using namespace std;
int n,m,ans;
char a[105][105];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
void dfs(int x,int y){if(x<0||y<0||x>=n||y>=m) return ;a[x][y]='0';for(int i=0;i<4;i++){int xx=x+dx[i],yy=y+dy[i];if(xx>=0&&xx<n&&yy>=0&&yy<m){if(a[xx][yy]!='0'){dfs(xx,yy);}}}
}
int main(){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]!='0'){dfs(i,j);ans++;}}}cout<<ans<<endl;return 0;
}P1331 海战
dfs(AC):
和细胞一样的思路,唯一需要注意的是对于斜着连着的情况要特殊输出
#include<iostream>
using namespace std;
int n,m,ans;
char a[1005][1005];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
bool flag;
void dfs(int x,int y){if(flag) return ;if(x<0||y<0||x>=n||y>=m) return ;a[x][y]='.';if(a[x-1][y+1]=='#'&&a[x-1][y]=='.'&&a[x][y+1]=='.') {flag=true; return ;}if(a[x+1][y+1]=='#'&&a[x+1][y]=='.'&&a[x][y+1]=='.') {flag=true; return ;}if(a[x+1][y-1]=='#'&&a[x+1][y]=='.'&&a[x][y-1]=='.') {flag=true; return ;}if(a[x-1][y-1]=='#'&&a[x-1][y]=='.'&&a[x][y-1]=='.') {flag=true; return ;}for(int i=0;i<4;i++){int xx=x+dx[i],yy=y+dy[i];if(xx>=0&&xx<n&&yy>=0&&yy<m){if(a[xx][yy]!='.'){dfs(xx,yy);}}}
}
int main(){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]!='.'){dfs(i,j);ans++;}}}if(!flag) cout<<"There are "<<ans<<" ships."<<endl;else cout<<"Bad placement."<<endl;return 0;
}B3625 迷宫寻路
dfs(AC):
#include<iostream>
using namespace std;
int n,m;
char a[105][105];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
void dfs(int x,int y){if(a[x-1][y]=='#'){if(a[x][y+1]=='#'){if(a[x+1][y]=='#'){if(a[x-1][y]=='#'){return ;}}}}for(int i=0;i<4;i++){int xx=x+dx[i],yy=y+dy[i];if(xx>0&&xx<=n&&yy>0&&yy<=m&&a[xx][yy]=='.'){a[xx][yy]='#';dfs(xx,yy);}}
}
int main(){cin>>n>>m;for(int i=0;i<=m+1;i++) a[0][i]='#',a[n+1][i]='#';for(int i=1;i<=n;i++) a[i][0]='#',a[i][m+1]='#';for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j];dfs(1,1);if(a[n][m]=='#') cout<<"Yes"<<endl;else cout<<"No"<<endl;return 0;
}bfs(AC):
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
typedef pair<int,int> pii;
int n,m,d[105][105];
char a[105][105];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int bfs(){queue<pii>q;q.push({0,0});memset(d,-1,sizeof d);d[0][0]=0;while(q.size()){auto t=q.front();q.pop();for(int i=0;i<4;i++){int x=t.first+dx[i],y=t.second+dy[i];if(x>=0&&x<n&&y>=0&&y<m&&a[x][y]=='.'&&d[x][y]==-1){d[x][y]=d[t.first][t.second]+1;q.push({x,y});}}}return d[n-1][m-1];
}
int main(){cin>>n>>m;for(int i=0;i<n;i++) cin>>a[i];if(bfs()==-1) cout<<"No"<<endl;else cout<<"Yes"<<endl;return 0;
}P1162 填涂颜色
思路:
利用dfs把原来的0变成1,并且标记数组记住原来的0,方便后续输出
然后图中剩下的1就是1,剩下的0就是2,输出即可
#include<iostream>
using namespace std;
const int N=35;
int n,a[N][N],flag[N][N];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
void dfs(int x,int y){a[x][y]=1;flag[x][y]=1;if(a[x-1][y]==1){if(a[x][y+1]==1){if(a[x+1][y]==1){if(a[x][y-1]==1){return ;}}}}for(int i=0;i<4;i++){int xx=x+dx[i],yy=y+dy[i];if(xx>0&&xx<=n&&yy>0&&yy<=n&&a[xx][yy]==0){dfs(xx,yy);}}
}
int main(){cin>>n;for(int i=0;i<=n+1;i++) a[0][i]=1,a[n+1][i]=1;for(int i=1;i<=n;i++) a[i][0]=-1,a[i][n+1]=-1;for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>a[i][j];for(int i=1;i<=n;i++){if(a[1][i]==0) {flag[1][i]=1;dfs(1,i);}if(a[n][i]==0) {flag[n][i]=1;dfs(n,i);}}for(int i=1;i<=n-1;i++){if(a[i][1]==0) {flag[i][1]=1;dfs(i,1);}if(a[i][n]==0) {flag[i][n]=1;dfs(i,n);}}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(flag[i][j]) cout<<"0"<<" ";else{if(a[i][j]) cout<<"1"<<" ";else cout<<"2"<<" ";}}cout<<endl;}return 0;
}P1506 拯救oibh总部
和上面几题一样的思路dfs(AC):
#include<iostream>
using namespace std;
const int N=505;
int n,m,ans;
char a[N][N];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
void dfs(int x,int y){a[x][y]='*';if(a[x-1][y]=='*'&&x-1>=0&&x-1<n&&y>=0&&y<m-1){if(a[x][y+1]=='*'&&x>=0&&x<n&&y+1>=0&&y+1<m-1){if(a[x+1][y]=='*'&&x+1>=0&&x+1<n&&y>=0&&y<m-1){if(a[x][y-1]=='*'&&x>=0&&x<n&&y-1>=0&&y-1<m-1){return ;}}}}for(int i=0;i<4;i++){int xx=x+dx[i],yy=y+dy[i];if(a[xx][yy]=='0'&&xx>=0&&xx<n&&yy>=0&&yy<m){dfs(xx,yy);}}
}
int main(){cin>>n>>m;for(int i=0;i<n;i++) cin>>a[i];for(int i=0;i<m;i++){if(a[0][i]=='0') dfs(0,i);if(a[n-1][i]=='0') dfs(n-1,i);}for(int i=1;i<n-1;i++){if(a[i][0]=='0') dfs(i,0);if(a[i][m-1]=='0') dfs(i,m-1);}for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(a[i][j]=='0') ans++;cout<<ans<<endl;return 0;
}P8662 [蓝桥杯 2018 省 AB] 全球变暖
这题非常重要的一点是:原来的岛屿经过海水淹没后(只要没完全被淹没),仍然认为他们是同一座岛屿!!!
模拟下图样例:
海平面上升后:
答案为:4(原来有8个岛屿,红色是没有被完全淹没的,那么被完全淹没的就有4个)
因此思路是:先dfs所有原来的岛屿,接着dfs没被完全淹没的岛屿,最后相减得结果(AC):
#include<iostream>
using namespace std;
const int N=1005;
char a[N][N],b[N][N];
int n,res,ans;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
void dfs_all(int x,int y){b[x][y]='.';if(b[x-1][y]=='.'&&x-1>=0&&x-1<n&&y>=0&&y<n){if(b[x][y+1]=='.'&&x>=0&&x<n&&y+1>=0&&y+1<n){if(b[x+1][y]=='.'&&x+1>=0&&x+1<n&&y>=0&&y<n){if(b[x][y-1]=='.'&&x>=0&&x<n&&y-1>=0&&y-1<n){return ;}}}}for(int i=0;i<4;i++){int xx=x+dx[i],yy=y+dy[i];if(b[xx][yy]=='#'){dfs_all(xx,yy);}}
}
void dfs_rest(int x,int y){a[x][y]='.';if(a[x-1][y]=='.'&&x-1>=0&&x-1<n&&y>=0&&y<n){if(a[x][y+1]=='.'&&x>=0&&x<n&&y+1>=0&&y+1<n){if(a[x+1][y]=='.'&&x+1>=0&&x+1<n&&y>=0&&y<n){if(a[x][y-1]=='.'&&x>=0&&x<n&&y-1>=0&&y-1<n){return ;}}}}for(int i=0;i<4;i++){int xx=x+dx[i],yy=y+dy[i];if(a[xx][yy]=='*'||a[xx][yy]=='#'){dfs_rest(xx,yy);}}
}
int main(){cin>>n;for(int i=0;i<n;i++) for(int j=0;j<n;j++) {cin>>a[i][j];b[i][j]=a[i][j];}for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(b[i][j]=='#') {dfs_all(i,j);res++;}for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(a[i][j]=='.'){for(int k=0;k<4;k++){int x=i+dx[k],y=j+dy[k];if(a[x][y]=='#') a[x][y]='*';}}}}for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(a[i][j]=='#') {dfs_rest(i,j);ans++;}cout<<res-ans<<endl;return 0;
}BFS(广搜)
模拟队列模板:
typedef pair<int,int>pii;
int mapp[N][N];
int d[N][N];//每一个点到起点的距离
pii q[N*N];//手写队列
int bfs(){int hh=0,tt=0;q[0]={0,0};memset(d,-1,sizeof d);//距离初始化为-1表示没有走过d[0][0]=0;//表示起点走过了int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};//方向向量while(hh <= tt){//队列不空auto t=q[hh++];//取走队头元素for(int i=0;i<4;i++){//枚举4个方向int x=t.first+dx[i],y=t.second+dy[i];//更新方向if(x>=0&&x<n&&y>=0&&y<m&&mapp[x][y]==0&&d[x][y]==-1){//在边界内并且是空地并且之前没有走过d[x][y]=d[t.first][t.second]+1;//更新距离q[++tt]={x,y};//新坐标入队}}}return d[n-1][m-1];//右下角距起点的距离
}STL模板:
typedef pair<int,int> pii;
int mapp[N][N],d[N][N];
int bfs(){queue<pii>q;q.push({0,0});memset(d,-1,sizeof d);d[0][0]=0;int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};while(q.size()){auto t=q.front();q.pop();for(int i=0;i<4;i++){int x=t.first+dx[i],y=t.second+dy[i];if(x>=0&&x<n&&y>=0&&y<m&&mapp[x][y]==0&&d[x][y]==-1){d[x][y]=d[t.first][t.second]+1;q.push({x,y});}}}return d[n-1][m-1];
}打印路径模板:
typedef pair<int,int> pii;
int mapp[N][N],d[N][N];
pii preNode[N][N];//存储每个点的前一个点的坐标,方便追踪路径
int bfs(){queue<pii>q;q.push({0,0});memset(d,-1,sizeof d);d[0][0]=0;int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};while(q.size()){auto t=q.front();q.pop();for(int i=0;i<4;i++){int x=t.first+dx[i],y=t.second+dy[i];if(x>=0&&x<n&&y>=0&&y<m&&mapp[x][y]==0&&d[x][y]==-1){d[x][y]=d[t.first][t.second]+1;preNode[x][y]=t;//记录前驱点,是由t走到(x,y)的q.push({x,y});}}}return d[n-1][m-1];
}
void print_path(){if(d[n-1][m-1]==-1){cout<<"无法抵达终点"<<endl;return ;}vector<pii>path;//从终点遍历追踪for(pii x={n-1,m-1};x!=make_pair(0,0);x=preNode[x.first][x.second]) path.push_back(x);path.push_back({0,0});//加入起点reverse(path.begin(), path.end());//将路径逆序for(auto x:path) cout<<"("<<x.first<<","<<x.second<<")"<<"->";cout<<"终点"<<endl;
}
bfs练习:
B3626 跳跃机器人
一维路径问题 bfs(AC):
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N=1e6+5;
int n,d[N];
int bfs(){queue<int>q;q.push({1});memset(d,-1,sizeof d);d[1]=0;while(q.size()){auto t=q.front();q.pop();if(t-1>=1&&t-1<=n&&d[t-1]==-1){d[t-1]=d[t]+1;q.push({t-1});}if(t+1>=1&&t+1<=n&&d[t+1]==-1){d[t+1]=d[t]+1;q.push({t+1});}if(2*t>=1&&2*t<=n&&d[2*t]==-1){d[2*t]=d[t]+1;q.push({2*t});}}return d[n];
}
int main(){cin>>n;cout<<bfs()<<endl;return 0;
}P2802 回家
二维路径问题+多种情况的判断 bfs(AC):
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=10;
int n,m,xbegin,ybegin;
struct point{ //结构体存储当前坐标状态int px,py,pstep,php;//坐标,步数,血量
};
int a[N][N]; //地图
bool flag[N][N];//标记经过鼠标
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int bfs(int x,int y){queue<point>q; //注意类型是结构体q.push(point{x,y,0,6});//出发点入队while(q.size()){auto t=q.front(); //取队头元素int x=t.px,y=t.py,step=t.pstep,hp=t.php;//初始化各变量q.pop(); //出队if(a[x][y]==3) return step;//走到家就结束if(hp>1){ //hp<=1时直接死亡for(int i=0;i<4;i++){int xx=x+dx[i],yy=y+dy[i];if(xx>=0&&xx<n&&yy>=0&&yy<m){//不能出界if(a[xx][yy]==1||a[xx][yy]==3){//路和家直接走q.push(point{xx,yy,step+1,hp-1});//入队}if(a[xx][yy]==4&&!flag[xx][yy]){//有鼠标的点最多只能走一次flag[xx][yy]=true;//标记q.push(point{xx,yy,step+1,6});//入队}}}}}return -1;//无解返回-1
}
int main(){cin>>n>>m;for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>a[i][j];if(a[i][j]==2) xbegin=i,ybegin=j;}}cout<<bfs(xbegin,ybegin)<<endl;return 0;
}P1135 奇怪的电梯
这题会卡纯的dfs,当然也可以搜索每一条路后就更新答案再继续搜索(未AC 64points):
#include<iostream>
using namespace std;
int n,a,b,k[205],ans=1e6,flag[205];
//当前在第x楼,按了cnt次按钮
void dfs(int x,int cnt){if(cnt>=ans) return ;if(x==b){ans=min(ans,cnt);return ;}flag[x]=1;if(x+k[x]<=n&&flag[x+k[x]]==0){ //上楼flag[x+k[x]]=1;dfs(x+k[x],cnt+1);flag[x+k[x]]=0;}if(x-k[x]>=1&&flag[x-k[x]]==0){ //下楼flag[x-k[x]]=1;dfs(x-k[x],cnt+1);flag[x-k[x]]=0;}
}
int main(){cin>>n>>a>>b;for(int i=1;i<=n;i++) cin>>k[i];dfs(a,0);if(ans==1e6) {cout<<"-1"<<endl; return 0;}cout<<ans<<endl;return 0;
}bfs(AC):
#include<iostream>
#include<queue>
using namespace std;
const int N=205;
int n,A,B,lift[N];
bool flag[N];
//标记数组作用是保证当前位置没有来过,因为如果回到原来经过的位置,那么就会一直重复
struct point{int loc,ans;//位置,当前已经走的步数
};
int bfs(int a,int b){queue<point>q;q.push(point{a,0});while(q.size()){auto t=q.front();int location=t.loc,step=t.ans;q.pop();if(location==b) return step;//到达终点if(location+lift[location]<=n){//可以向上if(!flag[location+lift[location]]){//并且该位置没有来过flag[location+lift[location]]=true;q.push(point{location+lift[location],step+1});}}if(location-lift[location]>=1){//可以向下if(!flag[location-lift[location]]){//并且该位置没有来过flag[location-lift[location]]=true;q.push(point{location-lift[location],step+1});}}}return -1;
}
int main(){cin>>n>>A>>B;for(int i=1;i<=n;i++) cin>>lift[i];cout<<bfs(A,B)<<endl;return 0;
}P1747 好奇怪的游戏
这题注意初始化flag标记数组,并且把数组开大一点就没问题了
bfs(AC):
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=50;
int x1,y1,x2,y2;
int dx[12]={-2,-2,-1,-2,1,-2,2,-1,2,1,2,2};
int dy[12]={-2,-1,-2,1,-2,2,-2,2,-1,2,1,2};
bool flag[N][N];
struct point{int px,py,pstep;//坐标,步数
};
int bfs(int a,int b){queue<point>q;q.push(point{a,b,0});memset(flag,0,sizeof flag);flag[a][b]=true;while(q.size()){auto t=q.front();q.pop();int x=t.px,y=t.py,step=t.pstep;if(x==1&&y==1) return step;for(int i=0;i<12;i++){int xx=x+dx[i],yy=y+dy[i];if(xx>=1&&yy>=1){if(!flag[xx][yy]){flag[xx][yy]=true;q.push(point{xx,yy,step+1});}}}}
}
int main(){cin>>x1>>y1>>x2>>y2;cout<<bfs(x1,y1)<<endl;cout<<bfs(x2,y2)<<endl;return 0;
}P1443 马的遍历
方法类似,只需要额外开一个二维答案数组存储步数即可
bfs(AC):
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=405;
int n,m,x,y;
int dx[8]={-2,-1,-2,1,-1,2,1,2};
int dy[8]={-1,-2,1,-2,2,-1,2,1};
int ans[N][N];//答案矩阵
bool flag[N][N];
struct point{int px,py;//坐标
};
void bfs(int a,int b){ans[a][b]=0;flag[a][b]=true;queue<point>q;q.push(point{a,b});while(q.size()){auto t=q.front();q.pop();int x=t.px,y=t.py;for(int i=0;i<8;i++){int xx=x+dx[i],yy=y+dy[i];if(xx>=1&&xx<=n&&yy>=1&&yy<=m){if(!flag[xx][yy]){flag[xx][yy]=true;q.push(point{xx,yy});ans[xx][yy]=ans[x][y]+1;}}}}return ;
}
int main(){cin>>n>>m>>x>>y;memset(ans,-1,sizeof ans);memset(flag,0,sizeof flag);bfs(x,y);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cout<<ans[i][j]<<" ";}cout<<endl;}return 0;
}P1746 离开中山路
bfs(AC):
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=1005;
int n,x1,x2,y1,y2;
char a[N][N];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
bool flag[N][N];
struct point{int px,py,ps;
};
int bfs(int bx,int by,int ex,int ey){queue<point>q;q.push(point{bx,by,0});flag[bx][by]=true;while(q.size()){auto t=q.front();int x=t.px,y=t.py,step=t.ps;q.pop();if(x==ex&&y==ey) return step;for(int i=0;i<4;i++){int xx=x+dx[i],yy=y+dy[i];if(xx>=1&&xx<=n&&yy>=1&&yy<=n){if(a[xx][yy]=='0'){if(!flag[xx][yy]){flag[xx][yy]=true;q.push(point{xx,yy,step+1});}}}}}return -1;
}
int main(){cin>>n;for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>a[i][j];cin>>x1>>y1>>x2>>y2;cout<<bfs(x1,y1,x2,y2)<<endl;return 0;
}P3395 路障
这题整体思路不变,唯一要加的是唯一需要注意的是路障的处理,可开一个block数组存放在(x,y)位置路障将在什么时候放下,对于没有路障的点,直接走过,对于有路障的点,判断时间即可
bfs(AC):
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=1005;
int T,n,a[N][N],block[N][N];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
bool flag[N][N];
struct point{int px,py,pt;//坐标,时间
};
bool bfs(){queue<point>q;q.push(point{1,1,0});flag[1][1]=true;while(!q.empty()){auto t=q.front();int x=t.px,y=t.py,timee=t.pt;q.pop();if(x==n&&y==n) return true;timee++;for(int i=0;i<4;i++){int xx=x+dx[i],yy=y+dy[i];if(xx>=1&&xx<=n&&yy>=1&&yy<=n){if(a[xx][yy]==0&&!flag[xx][yy]){flag[xx][yy]=true;if(!block[xx][yy]||timee<=block[xx][yy]){q.push(point{xx,yy,timee});}}}}}return false;
}
int main(){cin>>T;while(T--){memset(flag,0,sizeof flag);memset(block,0,sizeof block);memset(a,0,sizeof a);cin>>n;for(int i=1;i<=2*n-2;i++){int a1,b1;cin>>a1>>b1;block[a1][b1]=i;}if(bfs()) cout<<"Yes"<<endl;else cout<<"No"<<endl;}return 0;
}P8673 [蓝桥杯 2018 国 C] 迷宫与陷阱
和 P2802 回家 类似,
三维状态数组+多种情况判断 bfs(AC):
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=1005;
int n,k;
char a[N][N];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
//flag[x][y][z]:在剩余z个无敌时间时,有没有经过(x,y)
bool flag[N][N][11];
struct point{int px,py,ps,pk;//坐标,当前走的步数,剩余无敌的步数
};
int bfs(){queue<point>q;q.push({1,1,0,0});flag[1][1][0]=true;while(!q.empty()){auto t=q.front();q.pop();int x=t.px,y=t.py,step=t.ps,temp=t.pk;if(x==n&&y==n) return step;//到达终点,直接结束for(int i=0;i<4;i++){int xx=x+dx[i],yy=y+dy[i];if(xx>=1&&xx<=n&&yy>=1&&yy<=n){//保证边界if(a[xx][yy]!='#'){//墙是永远不可能经过的//当前是未使用过的道具if(a[xx][yy]=='%'&&!flag[xx][yy][k]){flag[xx][yy][k]=true;q.push({xx,yy,step+1,k});}//当前状态是无敌,道路和陷阱都可以走if(temp>0&&!flag[xx][yy][temp-1]){flag[xx][yy][temp-1]=true;q.push({xx,yy,step+1,temp-1});}//当前状态不是无敌,道路可以走if(temp==0&&a[xx][yy]=='.'&&!flag[xx][yy][0]){flag[xx][yy][0]=true;q.push({xx,yy,step+1,0});}}}}}return -1;
}
int main(){cin>>n>>k;for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>a[i][j];cout<<bfs()<<endl;return 0;
}P1141 01迷宫
暴力bfs (超时未AC 70points):
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=1e3+5;
char a[N][N];
bool flag[N][N];
int n,m,ans;
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
int bfs(int tx,int ty){ans=1;flag[tx][ty]=1;queue<pair<int,int>>q;q.push({tx,ty});while(!q.empty()){auto t=q.front();int x=t.first,y=t.second;q.pop();for(int i=0;i<4;i++){int xx=x+dx[i],yy=y+dy[i];if(xx>=1&&xx<=n&&yy>=1&&yy<=n){if(!flag[xx][yy]&&a[xx][yy]!=a[x][y]){flag[xx][yy]=1;ans++;q.push({xx,yy});}}}}return ans;
}
int main(){cin>>n>>m;for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>a[i][j];while(m--){int ax,bx;cin>>ax>>bx;memset(flag,0,sizeof flag);cout<<bfs(ax,bx)<<endl;}return 0;
}优化思路:
联通块上每一个点的答案等于该联通块的数目
注意这里的联通块指的是四个方向上0,1相间隔的联通块,如下图,在搜 a[1][2] 时会经过6个点,而这6个点的答案是一样的,都是6,因此通过搜完联通块直接给联通块上的所有点存答案即可
因此可以考虑 dfs+记忆化搜索(AC):
#include<iostream>
using namespace std;
const int N=1e3+5;
char a[N][N];//地图
int ans[N][N];//答案数组为0表示没有搜过,大于0表示答案
int temp[N*N][2];//记忆化,存储坐标数组
int n,m,res;
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
void dfs(int x,int y){res++;//搜到,答案自增//记忆化:存储坐标temp[res][0]=x;temp[res][1]=y;//ans数组当前只起标记作用ans[x][y]=1;for(int i=0;i<4;i++){int xx=x+dx[i],yy=y+dy[i];if(xx>=1&&xx<=n&&yy>=1&&yy<=n){if(a[x][y]!=a[xx][yy]){if(!ans[xx][yy]){dfs(xx,yy);}}}}return ;
}
int main(){cin>>n>>m;for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>a[i][j];while(m--){int ax,bx;cin>>ax>>bx;res=0;//已经存储过答案直接输出if(ans[ax][bx]) cout<<ans[ax][bx]<<endl;else{//否则搜素dfs(ax,bx);//记忆化:把路径上所有点的答案存储//ans数组正式记录所有答案for(int i=1;i<=res;i++)ans[temp[i][0]][temp[i][1]]=res;cout<<res<<endl;}}return 0;
}
