papala @ 2024-07-20 15:43:15
#include<bits/stdc++.h>
using namespace std;
const int N = 5100;
int n, m;
struct node {
int x, y;
} p[N * N];
//queue<pair<int,int> >q;
//pair<int,int> p[N*N];
int head, tail;
char mp[N][N];
bool mk[N][N];
bool flag;
int dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0};
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> mp[i][j];
}
}
head = tail = 1;
p[tail].x = 1, p[tail].y = 1;
tail++;
mk[p[head].x][p[head].y] = true;
while (head<tail) {
for (int i = 0; i < 4; i++) {
int tx = p[head].x + dx[i];
int ty = p[head].y + dy[i];
if (tx < 1 || tx > m || ty < 1 || ty > n) {
continue;
}
if (mp[tx][ty] != '#' && mk[tx][ty] == false) {
p[tail].x = tx, p[tail].y = ty ;
tail++;
mk[tx][ty] = true;
}
if (tx == m && ty == n) {
flag = true;
break;
}
}
if (flag) {
break;
}
head++;
}
if(flag)cout<<"Yes";
else cout<<"No";
return 0;
}
by LHX_18460366315 @ 2024-07-20 15:45:36
@papala 我的代码:
#include<bits/stdc++.h>
using namespace std;
//方向变量
const int dx[4] = {0,1,0,-1};
const int dy[4] = {1,0,-1,0};
int n,m,mark[1000][1000];
char Map[1000][1000];
//判断(x,y)是否在地图里面
bool isinmap(int x,int y){
return (x > 0 && x <= n && y > 0 && y <= m);
}
void dfs(int x,int y){
//到终点直接返回
if (x == n && y == m){
return;
}
//遍历四个方向
for (int i = 0;i < 4;i++){
int next_x = x + dx[i];
int next_y = y + dy[i];
//三个条件:在地图内,没有被走过,不是墙
if (isinmap(next_x,next_y) &&
!mark[next_x][next_y] &&
Map[next_x][next_y] != '#'){
//标记
mark[next_x][next_y] = 1;
//向下搜索
dfs(next_x,next_y);
}
}
}
int main(){
cin >> n >> m;
for (int i = 1;i <= n;i++){
for (int j = 1;j <= m;j++){
cin >> Map[i][j];
}
}
//从起点深搜
mark[1][1] = 1;
dfs(1,1); //从 map(1,1) 开始
if (mark[n][m]) cout << "Yes" << endl; //走到终点
else cout << "No" << endl;
return 0;
}
by papala @ 2024-07-20 16:38:10
谢谢(^-^)V