从易到难,萌新往这里看!!
2024-11-02 21:35:23
发布于:广东
7阅读
0回复
0点赞
我看大家都只用了一种方法,我这里介绍两种方法!萌新往这里看!
第一种(最简单的)深度优先搜索:
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int dx[4] = {1,-1,0,0},dy[4] = {0,0,1,-1};
int vis[105][105];
char mp[105][105];
int n,m,sx,sy,fx,fy;
bool flag;
struct node{
int x,y,prev;
};
//深搜的函数
void DFS(int x,int y){
if(flag == 1) return;
if(x == n - 1 and y == m - 1){
flag = 1;
return;
}
for(int i = 0;i < 4;i ++){
int nx = x + dx[i],ny = y + dy[i];
if(vis[nx][ny] == 0 and nx >= 0 and ny >= 0 and nx < n and ny < m and mp[nx][ny] == '0'){//判定
vis[nx][ny] = 1;
DFS(nx,ny);//递归
vis[nx][ny] = 0;
}
}
}
int main(){
cin >> n >> m;
for(int i = 0;i < n;i ++){
for(int j = 0;j < m;j ++){
cin >> mp[i][j];
}
}
cin >> sx >> sy >> fx >> fy;
DFS(0,0);
if(flag == 0){
cout << "NO";
} else {
cout << "YES";
}
return 0;
}
最后的方法:
用栈实现深搜(好吧,可能是我真的没事做)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int dx[4] = {1,-1,0,0},dy[4] = {0,0,1,-1};
int vis[105][105];
char mp[105][105];
int n,m,sx,sy,fx,fy;
bool flag;
struct node{
int x,y;
};
int main(){
cin >> n >> m;
for(int i = 0;i < n;i ++){
for(int j = 0;j < m;j ++){
cin >> mp[i][j];
}
}
stack<node> stk;
stk.push({0,0});// 分别是 x y 上一个节点(用来打到深搜回溯的效果)
vis[sx][sy] = 1;
while(!stk.empty()){
int ix = stk.top().x,iy = stk.top().y,iprev = stk.top().prev;
stk.pop();
if(ix == n - 1 and iy == m - 1){
flag = 1;
break;
}
for(int i = 0;i < 4;i ++){
int nx = ix + dx[i],ny = iy + dy[i];
if(vis[nx][ny] == 0 and nx >= 0 and ny >= 0 and nx < n and ny < m and mp[nx][ny] == '0'){//判定
vis[ix][iy] ++;
stk.push({nx,ny);
}
}
}
if(flag == 0){
cout << "NO";
} else {
cout << "YES";
}
return 0;
}
广搜当然也能做(我不展示了)
这里空空如也
有帮助,赞一个