c++ class类bfs模板题目

thj的博客 / 2023-05-14 / 原文

题目网址：走迷宫 - 题目 - Liuser's OJ (cpolar.cn)

原本代码（bfs广度优先搜索）：

#include<bits/stdc++.h>

using namespace std;

const int N=50;
int n,m;
int sx,sy;
char a[N][N];
int b[N][N];
bool vis[N][N];
int dx[]={1,0,-1,0};
int dy[]={0,-1,0,1};
struct node{
    int x;
    int y;
};
queue<node> q;

int bfs(int x,int y){
    node s={x,y};
    q.push(s);
    while(!q.empty()){
        node t=q.front();
        q.pop();
        if(a[t.x][t.y]=='T') return b[t.x][t.y];
        for(int i=0;i<4;i++){
            node nt;
            nt.x=t.x+dx[i];
            nt.y=t.y+dy[i];
            if(nt.x>=1 and nt.y>=1 and nt.x<=n and nt.y<=m and vis[nt.x][nt.y]==false and a[nt.x][nt.y]!='#'){
                vis[nt.x][nt.y]=true;
                b[nt.x][nt.y]=b[t.x][t.y]+1;
                q.push(nt);
            }
        }
    }
    return -1;
}    

int main(){
    memset(b,0,sizeof(b));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            if(a[i][j]=='S') sx=i,sy=j;
        }
    }
    vis[sx][sy]=true;
    int ans=bfs(sx,sy);
    printf("%d\n",ans);
    return 0;
}

然后我花了大概三个两分半写成了昨天自学学的类（我不知道为什么编程老师不教类）：

#include<bits/stdc++.h>

using namespace std;

const int N=60;
int dx[]={1,0,-1,0};
int dy[]={0,-1,0,1};
int sx,sy;
struct node{
    int x;
    int y;
};
queue<node> q;

class Box{
    public:
        int n,m;
        char a[N][N];
        int vis[N][N];
        int sr(){
            int sx,sy;
            memset(vis,0,sizeof(vis));
            for(int i=1;i<=n;i++){
                for(int j=1;j<=m;j++){
                    cin>>a[i][j];
                    if(a[i][j]=='S') sx=i,sy=j;
                }
            }
            return bfs(sx,sy);
        }
        int bfs(int x,int y){
            vis[x][y]=1;
            node s={x,y};
            q.push(s);
            while(!q.empty()){
                node t=q.front();
                q.pop();
                if(a[t.x][t.y]=='T') return vis[t.x][t.y]-1;
                for(int i=0;i<4;i++){
                    node nt;
                    nt.x=t.x+dx[i];
                    nt.y=t.y+dy[i];
                    if(nt.x>=1 and nt.y>=1 and nt.x<=n and nt.y<=m and vis[nt.x][nt.y]==0 and a[nt.x][nt.y]!='#'){
                        vis[nt.x][nt.y]=vis[t.x][t.y]+1;
                        q.push(nt);
                    }
                }
            }
            return -1;
        }
};

int main(){
    Box box;
    cin>>box.n>>box.m;
    int ans;
    ans=box.sr();
    cout<<ans<<endl;
    return 0;
}