day02
2026-08-08 14:54:25
发布于：广东
74阅读
0回复
0点赞
广搜模版
/*
queue<需要存的类型> q;
q.push(x) //x入队
q.pop() //队首出队
q.front() //拿队首
q.size() //队列长度
q.empty() //判断队列是否为空
*/
/*
q.push({sx,sy}); //起点入队
vis[sx][sy] = 1; //标记起点已访问
while(q.size()){ //队列不为空
ll x = q.front().x; //拿到队首元素
ll y = q.front().y;
q.pop(); //出队
for(ll i=0;i<4;i++){ //访问四个方向
ll nx = x + dx[i]; //下一个要访问的点
ll ny = y + dy[i];
if(是否越界)continue;
if(vis[nx][ny])continue;
if(是否是障碍物)continue;
vis[nx][ny] = 1; //标记下一个点已访问
q.push({nx,ny}); //下一个点入队
}
*/
/*
#include<bits/stdc++.h>
using namespace std;
using ll=long long ;
const ll N = 1e3 + 10;
ll dx[] = {0,0,1,-1};
ll dy[] = {1,-1,0,0};
ll vis[N][N];
ll ma[N][N];
ll n,m,fx,fy;
struct node{
ll x,y,step;
};
queue<node>q;
void bfs(ll sx,ll sy){ //代表当前点
q.push({sx,sy,0}); //起始点入队
vis[sx][sy] = 1; //标记起始点
while(q.size()){
ll x = q.front().x; //当前点
ll y = q.front().y;
ll step = q.front().step;
q.pop();
if(x==fx&&y==fy){
cout<<step;
exit(0);
}
for(ll i = 0; i < 4 ; i++){
ll nx = x + dx[i]; //代表下一个点
ll ny = y + dy[i];
//判断(nx,ny)这个点能不能走
//1、是否越界
if(nx<1||nx>n||ny<1||ny>m) continue;
//2、是否访问过
if(vis[nx][ny]) continue;
//3、是否是障碍物
if(ma[nx][ny]=='#') continue;
q.push({nx,ny,step+1});
vis[nx][ny] = 1;
}
}
}
int main(){
bfs(1,1);
bfs(sx,sy);
cout<<-1;
return 0;
}
*/
第二题
ll dx[] = {0,0,1,-1};
ll dy[] = {1,-1,0,0};
char ma[20][20];
bool vis[20][20];
struct node{
ll x,y,step;
};
ll n,m;
void bfs(ll sx,ll sy){
queue<node> q;
q.push({sx,sy,0});
vis[sx][sy] = 1;
while(q.size()){
ll x = q.front().x;
ll y = q.front().y;
ll step = q.front().step;
q.pop();
if(x==n&&y==m){
cout<<step;exit(0);
}
for(ll i=0;i<4;i++){
ll nx = x + dx[i];
ll ny = y + dy[i];
if(nx<1||nx>n||ny<1||ny>m)continue;
if(vis[nx][ny])continue;
if(ma[nx][ny]=='#')continue;
vis[nx][ny] = 1;
q.push({nx,ny,step+1});
}
}
}
int main() {
cin>>n>>m;
for(ll i = 1; i <= n ; i++){
for(ll j = 1; j <= m ; j++){
cin>>ma[i][j];
}
}
bfs(1,1);
cout<<-1;
return 0;
}
第三题
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
ll n,m,ans;
vector<ll> v[N]; //定义邻接表
bool vis[N];
queue<ll> q;
void bfs(ll sx){
vis[sx] = 1;
q.push(sx);
ans++;
while(q.size()){
ll x = q.front(); //当前点
q.pop();
for(ll i = 0; i < v[x].size() ; i++){
ll u = v[x][i];
if(!vis[u]){
q.push(u);
vis[u] = 1;
}
}
}
}
int main() {
cin>>n>>m;
for(ll i = 1; i <= m ; i++){//存图
ll x,y;
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
ll x,y;cin>>x>>y;
bfs(x);
if(vis[y]) cout<<ans;
else cout<<0;
return 0;
}
第四题
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
ll n,m,ans;
vector<ll> v[N]; //定义邻接表
bool vis[N];
queue<ll> q;
void bfs(ll sx){
vis[sx] = 1;
q.push(sx);
ans++;
while(q.size()){
ll x = q.front(); //当前点
q.pop();
for(ll i = 0; i < v[x].size() ; i++){
ll u = v[x][i];
if(!vis[u]){
q.push(u);
vis[u] = 1;
ans++;
}
}
}
}
int main() {
cin>>n>>m;
for(ll i = 1; i <= m ; i++){//存图
ll x,y;
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
ll x,y;cin>>x>>y;
bfs(x);
if(vis[y]) cout<<ans;
else cout<<0;
return 0;
}
第五题
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
char ma[1100][1100];
ll dis[1100][1100];
ll dx[] = {0,0,-1,1};
ll dy[] = {1,-1,0,0};
struct node{
ll x,y;
};
ll n,m;
queue<node> q;
void bfs(){
while(q.size()){
ll x = q.front().x;
ll y = q.front().y;
q.pop();
for(ll i = 0; i < 4 ; i++){
ll nx = x + dx[i];
ll ny = y + dy[i];
if(nx<1||nx>n||ny<1||ny>m) continue;
if(ma[nx][ny]=='#') continue;
if(dis[x][y]+1>=dis[nx][ny]&&dis[nx][ny]!=-1) continue;
dis[nx][ny] = dis[x][y] + 1;
q.push({nx,ny});
}
}
}
int main() {
cin>>n>>m;
for(ll i = 1; i <= n ; i++){
for(ll j = 1; j <= m ; j++){
cin>>ma[i][j];
dis[i][j] = -1;
if(ma[i][j] == '#'){
q.push({i,j});
dis[i][j] = 0;
}
}
}
bfs();
ll ans = 0;
for(ll i = 1; i <= n ; i++){
for(ll j = 1; j <= m ; j++){
ans = max(dis[i][j],ans);
}
}
cout<<ans;
return 0;
}
第12题
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e5 + 10;
ll n,k;
queue<ll> q;
ll dis[N];
void bfs(ll sx){
q.push(sx);
dis[sx] = 0;
while(q.size()){
ll x = q.front();q.pop();
if(x==k) return;
ll nx = x-1;
if(nx>=0&&dis[nx]==-1){
q.push(nx);
dis[nx] = dis[x] + 1;
}nx = x+1;
if(nx<=100000&&dis[nx]==-1){
q.push(nx);
dis[nx] = dis[x] + 1;
}nx = x*2;
if(nx<=100000&&dis[nx]==-1){
q.push(nx);
dis[nx] = dis[x] + 1;
}
}
}
int main() {
cin>>n>>k;
memset(dis,-1,sizeof(dis));
bfs(n);
cout<<dis[k];
return 0;
}
有帮助，赞一个