10分求助

B3625 迷宫寻路

Mark_M @ 2023-09-13 00:41:38

我真的找不到我错在哪里，但就是10分

第一次：

#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#define N 105
using namespace std;
const int dir[4][2] = { {1,0},{0,1},{-1,0},{0,-1} };
int n, m;
bool vis[N][N];
char mat[N][N];
queue<pair<int, int>> q;
bool flag = false;

void bfs() {
    while (!q.empty() && flag == false) {
        pair<int, int> now;
        now = q.front();
        q.pop();
        int x = now.first;
        int y = now.second;
        vis[x][y] = true;

        for (int i = 0; i < 4; i++) {
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];
            if (nx <= 0 || nx > n || ny <= 0 || ny > m || mat[nx][ny] == '#' || vis[nx][ny] == true) {
                continue;
            }
            q.push(make_pair(nx, ny));
            if (nx == n && ny == m) {
                flag = true;
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> mat[i][j];
        }
    }
    if (mat[n][m] == '#' || mat[1][1] == '#') {
        cout << "No" << endl;
        return 0;
    }

    q.push(make_pair(1, 1));
    bfs();

    if (flag) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
    return 0;
}

1AC+9TLE

第二次：（31行处加了一个return，我个人觉得不影响）

#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#define N 105
using namespace std;
const int dir[4][2] = { {1,0},{0,1},{-1,0},{0,-1} };
int n, m;
bool vis[N][N];
char mat[N][N];
queue<pair<int, int>> q;
bool flag = false;

void bfs() {
    while (!q.empty() && flag == false) {
        pair<int, int> now;
        now = q.front();
        q.pop();
        int x = now.first;
        int y = now.second;
        vis[x][y] = true;

        for (int i = 0; i < 4; i++) {
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];
            if (nx <= 0 || nx > n || ny <= 0 || ny > m || mat[nx][ny] == '#' || vis[nx][ny] == true) {
                continue;
            }
            q.push(make_pair(nx, ny));
            if (nx == n && ny == m) {
                flag = true;
                return;
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> mat[i][j];
        }
    }
    if (mat[n][m] == '#' || mat[1][1] == '#') {
        cout << "No" << endl;
        return 0;
    }

    q.push(make_pair(1, 1));
    bfs();

    if (flag) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
    return 0;
}

1AC+9MLE

有没有大佬说说这是为什么？

by liu_le_chen @ 2023-09-13 06:53:56

自己看看咯也是BFS @Mark_M

#include<bits/stdc++.h>
using namespace std;
long long n,m,f,flag[1001][1001],vis[4][2]={-1,0,1,0,0,-1,0,1};
char arr[1001][1001];
struct node{
    int x,y;
};
queue<node> q;
void bfs(){
    q.push({1,1});
    flag[1][1]=1;
    while(!q.empty()){
        for(int i=0;i<4;i++){
            int xx=q.front().x+vis[i][0];
            int yy=q.front().y+vis[i][1];
            if(arr[xx][yy]=='.' && flag[xx][yy]==0 && xx>=1 && xx<=n && yy>=1 && yy<=m){
                flag[xx][yy]=1;
                if(xx==n && yy==m){
                    cout<<"Yes";
                    f=0;
                    return;
                }
                q.push({xx,yy});
            }
        }
        q.pop();
    }
}
int main(){
    f=1;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>arr[i][j];
        }
    }
    bfs();
    if(f) cout<<"No";
    return 0;
}

求关！！！

by Mark_M @ 2023-09-13 18:12:50

@liulechen

必须关注，谢谢！