搜索在蓝桥杯省赛中占据较大比重考点的频率较高,对于我这样想先拿省一的菜鸡可谓是必拿下的分数
知乎上更有得搜索得蓝桥杯的说法
------>常见的与图相关的 算法标签为 DFS|BFS|Flood Fill算法
常见的【二维数组】【最短路]
思路分析 【BFS】【标记问题】
#include<bits/stdc++.h>
using namespace std;
//----------->在此处注意define 和 typedef 的定义方法相反即define x first 和 typedef first x
#define x first
#define y second
const int N=210;
typedef pair<int, int> PII;
char g[N][N];
int dist[N][N];
int t;
int st[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
void bfs(int x,int y,int f_x,int f_y,int a,int b){
queue<PII> q;
st[x][y]=true;
dist[x][y]=0;
q.push({x,y});
while(q.size()){
int x_f=q.front().x,y_f=q.front().y;
q.pop();
for(int i=0;i<4;i++){
int nx=x_f+dx[i],ny=y_f+dy[i];
if(nx>=0 && nx<a && ny>=0 && ny<b && !st[nx][ny] && g[nx][ny]!='#'){
st[nx][ny]=true;
dist[nx][ny]=dist[x_f][y_f]+1;
if(nx==f_x && ny==f_y)return ;
q.push({nx,ny});
}
}
}
}
|
|
|
|
->**维度升级**
常见的【三维数组】【最短路]
思路分析 【BFS】【标记问题】【改变二维pair的存储方式改为结构体】
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
const int N=210;
//-------------------->在此处使用结构体进行存储
struct PII{
int x,y,z;
};
char g[N][N][N];
int dist[N][N][N];
int t;
int st[N][N][N];
int dx[6] = {-1, 0, 1, 0, 0 , 0 }, dy[6] = {0, 1, 0, -1, 0 , 0},dz[6]{0, 0 ,0 ,0,1, -1};
void bfs(int x,int y,int z,int f_x,int f_y,int f_z,int a,int b,int c){
queue<PII> q;
memset(dist,-1,sizeof dist);
//st[x][y][z]=true;
dist[x][y][z]=0;
q.push({x,y,z});
while(q.size()){
//int x_f=q.front().x,y_f=q.front().y;
int x_f=q.front().x,y_f=q.front().y,z_f=q.front().z;
q.pop();
for(int i=0;i<6;i++){
int nx=x_f+dx[i],ny=y_f+dy[i],nz=z_f+dz[i];
if(nx>=0 && nx<a && ny>=0 && ny<b && nz>=0 && nz<c && (dist[nx][ny][nz] == -1) && g[nx][ny][nz]!='#'){
// st[nx][ny][nz]=true;
dist[nx][ny][nz]=dist[x_f][y_f][z_f]+1;
if(nx==f_x && ny==f_y && nz==f_z)return ;
q.push({nx,ny,nz});
}
}
}
}
int main(){
int a,b,c;
while(scanf("%d%d%d", &a, &b, &c), a || b || c){
/*----------->在本题中由于是三维数组，
如果使用st数组来对于每个位置进行标记，会超出空间复杂度,因此可以使用查看dist
下一个将要“走”到的位置的dist信息，如果dist[nx][ny][nz]==-1(-1为dist数组的初始值)则可以进行移动反之不可
*/
// memset(st, 0, sizeof st);
int start_x,start_y,start_z,end_x,end_y,end_z;
for(int j=0;j<a;j++){
for(int k=0;k<b;k++){
for(int q=0;q<c;q++){
cin>>g[j][k][q];
if(g[j][k][q]=='S'){
start_x=j,start_y=k,start_z=q;
}else if(g[j][k][q]=='E'){
end_x=j,end_y=k,end_z=q;
}
}
}
}
//st[start_x][start_y][start_z]=true;
bfs(start_x,start_y,start_z,end_x,end_y,end_z,a,b,c);
if(dist[end_x][end_y][end_z]==-1)cout<<"Trapped!"<<endl;
else {
printf("Escaped in %d minute(s).\n",dist[end_x][end_y][end_z]);
}
}
return 0;
}
常见的Flood Fill算法
思路分析:【Flood Fill】【DFS】
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
//洪水灌溉算法--->变形
typedef long long LL;
char g[N][N];
bool st[N][N];
int dist[N][N];
int n;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
void dfs(int x,int y,int &u){
if(g[x-1][y]!='.' && g[x+1][y]!='.' && g[x][y-1]!='.' && g[x][y+1]!='.'){
u++;
}
for(int i=0;i<4;i++){
int nx=x+dx[i],ny=y+dy[i];
if(nx>=0 && nx<n && ny>=0 && ny<n && !st[nx][ny] && g[nx][ny]!='.'){
st[nx][ny]=true;
// dist[nx][ny]=dist[x][y]+1;
dfs(nx,ny,u);
}
}
}
int ans;
int main(){
cin>>n;
memset(dist,-1,sizeof dist);
for(int i=0;i<n;i++){
cin>>g[i];
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(g[i][j]=='#' && !st[i][j]){
int u=1;
st[i][j]=true;
dfs(i,j,u);
if(u==1)ans++;
}
}
}
cout<<ans;
return 0;
}
