20pts 求调!!
查看原帖
20pts 求调!!
841612
xian_love楼主2024/7/30 10:28
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N = 310;
char g[N][N];//用于存地图的
int dist[N][N];//用于存起点到(i,j)的距离
bool vis[N][N];//记录这个点是否被访问过
typedef pair<int,int> PII;
int ansx,ansy,bx,by;
#define x first 
#define y second
queue <PII> q;
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1}; 
int bfs(int x1,int y1)
{
    memset(dist,-1,sizeof dist);
    memset(vis,false,sizeof vis);
    q.push({x1,y1});
    dist[x1][y1] = 0;
    vis[x1][y1] = true;
    
    while(!q.empty())
    {
        PII t = q.front();
        q.pop();
        //字母特判
        if(g[t.x][t.y] == '=')return dist[t.x][t.y]; 
        if(g[t.x][t.y] >= 'A'&&g[t.x][t.y] <= 'Z')
        {
            for(int i=1;i<=n;i++)
                for(int j=1;j<=m;j++)
                {
                    if(g[i][j] == g[t.x][t.y] && (i!=t.x||j!=t.y))
                    {
                        dist[i][j] = dist[t.x][t.y]; //值先赋好
                        t.x = i;
                        t.y = j;
                    }
                }
            
        }
        
        for(int i=0;i<4;i++)
        {
            int a = t.x + dx[i];
            int b = t.y + dy[i];
            
            if(g[a][b] == '#')continue;
            if(vis[a][b])continue;
            if(a>n||a<1||b<1||b>m)continue;
            
            q.push({a,b});
            vis[a][b] = true;
            dist[a][b] = dist[t.x][t.y] + 1; 
            //if(g[a][b] == '=')return dist[a][b];
        }
        
        
    }
    return dist[ansx][ansy];
}


int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            cin>>g[i][j];
            if(g[i][j] == '@'){bx = i;by = j;}
            if(g[i][j] == '='){ansx = i;ansy = j;}
        }
    int res = bfs(bx,by);
    cout<<res<<endl;
//    for(int i=1;i<=n;i++)
//    {
//		for(int j=1;j<=m;j++)cout<<dist[i][j]<<" ";
//		cout<<endl;}
    return 0;
}
2024/7/30 10:28
加载中...