请问怎么优化啊 这代码又臭又长

willix @ 2023-04-19 18:24:38

#include <bits/stdc++.h>
#define N 105
using namespace std;
int n, m;
bool vis[N][N];
void bfs(int x, int y) {
    queue<pair<int, int>> q;
    q.push(make_pair(x, y));
    vis[x][y]=true;
    while(!q.empty()) {
        pair<int, int> p=q.front();
        q.pop();
        int x1=p.first, y1=p.second;
        if(x1==m && y1==n) {
            cout << "Yes";
            return;
        }
        if(!vis[x1+1][y1]) {
            vis[x1+1][y1]=true;
            q.push(make_pair(x1+1, y1));
        }
        if(!vis[x1][y1+1]) {
            vis[x1][y1+1]=true;
            q.push(make_pair(x1, y1+1));
        }
        if(!vis[x1-1][y1]) {
            vis[x1-1][y1]=true;
            q.push(make_pair(x1-1, y1));
        }
        if(!vis[x1][y1-1]) {
            vis[x1][y1-1]=true;
            q.push(make_pair(x1, y1-1));
        }
    }
    cout << "No";
}
int main() {
    char a;
    cin >> n >> m;
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= m;j++) {
            cin >> a;
            if(a=='#') vis[j][i]=true;
        }
    }
    for(int i = 0;i <= n+1;i++) {
        vis[0][i]=vis[m+1][i]=true;
    }
    for(int i = 0;i <= m+1;i++) {
        vis[i][0]=vis[i][n+1]=true;
    }
    bfs(1, 1);
    return 0;
}

by JYW2011 @ 2023-04-19 18:27:57

你的代码有两个问题：

1. 进行 BFS 时，应该把行坐标和列坐标分别处理，而不是用 x1 和 y1 表示行和列。

2. 输入的二维矩阵中，行和列的顺序是反过来的。也就是说，实际上你应该读入的是一个 m\times n 的矩阵。因此处理边界时也需要注意调换行和列的顺序。

by zhuletian @ 2023-04-19 19:13:16

其实这道题用dfs更好

#include <iostream>
#include <string>
using namespace std;

int n, m;
string a[105];
bool f[105][105];

void dfs(int x, int y)
{
    if (x < 1 || x > n || y < 0 || y >= m || a[x][y] == '#' || f[x][y])  return;
    f[x][y] = true;
    if (x == n && y + 1 == m)  
    {
        cout << "Yes";
        exit(0);
    }
    dfs(x + 1, y);
    dfs(x - 1, y);
    dfs(x, y + 1);
    dfs(x, y - 1);
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    dfs(1, 0);
    cout << "No";
    return 0;
}

by TF58 @ 2023-04-24 17:37:42

试这个

#include<bits/stdc++.h>
using namespace std;
int n,m,a[110][110];
char ch;
bool flag;
int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};  //向上/下/左/右走的“标志型”数组
void dfs(int x,int y){
    if(x==n && y==m){
        flag=true;
        return;
    }   //到达终点就返回
    a[x][y]=1;
    for(int i=0;i<4;i++){
        int xx=x+dx[i];
        int yy=y+dy[i];
        if(xx<=0 || xx>n || yy<=0 || yy>m){
            continue;
        }   //判断是否“越界”
        if(a[xx][yy]==0) dfs(xx,yy);    //继续搜索
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>ch;
            if(ch=='#') a[i][j]=1;
        }
    }   //读入时，可用“1”表示墙，“0”表示空地
    if(a[1][1]==1 || a[n][m]==1){
        printf("No\n");
        return 0;
    }   //特判，如果起点或终点是墙
    dfs(1,1);
    if(flag) printf("Yes\n");
    else printf("No\n");
   return 0;
}

by wjl_100930 @ 2023-09-09 09:05:49

iakioi