当前位置:网站首页>[width first search] Ji Suan Ke: Suan tou Jun goes home (BFS with conditions)
[width first search] Ji Suan Ke: Suan tou Jun goes home (BFS with conditions)
2022-07-06 01:57:00 【muse_ age】
8 10
P.####.#P#
..#..#...#
..#T##.#.#
..........
..##.#####
..........
#####...##
###....S##
21
It is generally used to find the shortest number of steps BFS:
Conditional BFS:
Starting from S, The finish for T, When you reach the end, judge whether you have passed P( If two conditions are met at the same time, return )
Tag arrays use three-dimensional :
vis[x][y][flag]
vis One more dimension indicates whether the key has been obtained .
If the terminal is reached and the state of obtaining the key is marked ,bfs end .
You can actually walk twice at the same point , The first time was when I didn't get the key , The second time was when I got the key ?
Code :
#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<cstring>
using namespace std;
int n,m;
vector<string>G;
bool vis[2001][2001][2];
struct state{
int x,y;
int step;
bool flag;
state(int _x,int _y,int _step,bool _flag){
x=_x;
y=_y;
step=_step;
flag=_flag;
}
};
void input(){
cin>>n>>m;
for(int i=0;i<n;i++){
string s;
cin>>s;
G.push_back(s);
}
memset(vis,false,sizeof(vis));
}
void bfs(int x,int y){
queue<state>q;
q.push(state(x,y,0,false));
while(!q.empty()){
state cur=q.front();
q.pop();
int x=cur.x;
int y=cur.y;
int step=cur.step;
bool flag=cur.flag;
if(G[x][y]=='P'){
flag=true;
}
if(G[x][y]=='T'&&flag==true){
cout<<" They count :"<<step<<endl;
return;
}
vis[x][y][flag]=true;
if(x+1<n&&!vis[x+1][y][flag]&&G[x+1][y]!='#'){
vis[x+1][y][flag]=true;
q.push(state(x+1,y,step+1,flag));
}
if(x-1>=0&&!vis[x-1][y][flag]&&G[x-1][y]!='#'){
vis[x-1][y][flag]=true;
q.push(state(x-1,y,step+1,flag));
}
if(y-1>=0&&!vis[x][y-1][flag]&&G[x][y-1]!='#'){
vis[x][y-1][flag]=true;
q.push(state(x,y-1,step+1,flag));
}
if(y+1<m&&!vis[x][y+1][flag]&&G[x][y+1]!='#'){
vis[x][y+1][flag]=true;
q.push(state(x,y+1,step+1,flag));
}
}
}
void output(){
for(int i=0;i<n;i++){
cout<<G[i]<<endl;
}
}
void solve(){
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(G[i][j]=='S'){
bfs(i,j);
return;
}
}
}
}
int main(){
input();
solve();
}
边栏推荐
- Sword finger offer 38 Arrangement of strings
- PHP campus financial management system for computer graduation design
- Tensorflow customize the whole training process
- 剑指 Offer 12. 矩阵中的路径
- [flask] response, session and message flashing
- XSS learning XSS lab problem solution
- leetcode-两数之和
- How to set an alias inside a bash shell script so that is it visible from the outside?
- National intangible cultural heritage inheritor HD Wang's shadow digital collection of "Four Beauties" made an amazing debut!
- Ali test Open face test
猜你喜欢
Folio. Ink is a free, fast and easy-to-use image sharing tool
A basic lintcode MySQL database problem
Basic operations of databases and tables ----- primary key constraints
[detailed] several ways to quickly realize object mapping
Leetcode3, implémenter strstr ()
干货!通过软硬件协同设计加速稀疏神经网络
Redis如何实现多可用区?
[flask] official tutorial -part3: blog blueprint, project installability
[technology development -28]: overview of information and communication network, new technology forms, high-quality development of information and communication industry
Selenium waiting mode
随机推荐
How does redis implement multiple zones?
NLP fourth paradigm: overview of prompt [pre train, prompt, predict] [Liu Pengfei]
ClickOnce does not support request execution level 'requireAdministrator'
Initialize MySQL database when docker container starts
Ali test open-ended questions
PHP campus financial management system for computer graduation design
Thinking about the best practice of dynamics 365 development collaboration
竞赛题 2022-6-26
Blue Bridge Cup embedded_ STM32_ New project file_ Explain in detail
剑指 Offer 12. 矩阵中的路径
Flowable source code comments (36) process instance migration status job processor, BPMN history cleanup job processor, external worker task completion job processor
NumPy 数组索引 切片
Basic operations of databases and tables ----- primary key constraints
Sword finger offer 12 Path in matrix
Computer graduation design PHP part-time recruitment management system for College Students
Paddle框架:PaddleNLP概述【飛槳自然語言處理開發庫】
Flutter Doctor:Xcode 安装不完整
3D vision - 4 Getting started with gesture recognition - using mediapipe includes single frame and real time video
[flask] static file and template rendering
【Flask】官方教程(Tutorial)-part3:blog蓝图、项目可安装化