51分,第二个测试用例找不到出口
查看原帖
51分,第二个测试用例找不到出口
947842
aton_puck楼主2023/8/27 10:54

我把走过的'.'以及单个出现的字母标记为'#',成对的传送门不标记,第二个测试用例没有走到出口,找不到问题。。。

#include <iostream>
#include <queue>
using namespace std;
const int N = 310;

char maze[N][N];
int step[N][N];
int n,m;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
pair<int,int> My_find(int x, int y)
{
    for(int i=1 ; i<=n ; i++)
        for(int j=1 ; j<=m ; j++)
            if(maze[i][j] == maze[x][y] && i!=x)
                return {i,j};
    cout<<maze[x][y]<<endl;
    return {0,0};
}
int bfs(int x, int y)
{
    queue<pair<int,int>> q;
    q.push({x,y});
    maze[x][y] = '#';
    step[x][y] = 0;
    while(!q.empty())
    {
        int xx = q.front().first;
        int yy = q.front().second;
        q.pop();
        for(int i=0 ; i<4 ; i++)
        {
            int row = xx + dx[i];
            int col = yy + dy[i];
            if(row>=1&&row<=n && col>=1&&col<=m
                && maze[row][col]!='#')
                {
                    step[row][col] = step[xx][yy]+1;
                    if(maze[row][col] == '.')
                        maze[row][col] = '#';  //走过地路标记为墙
                    else if(maze[row][col] == '=')
                    {
                        return step[row][col];
                    }
                    else 
                    {
                        pair<int,int> p = My_find(row,col);  //找到传送点坐标
                        if(p.first == 0) maze[row][col] = '#';  //无法传送,标记为走过
                        else 
                        {                        //传送
                            row = p.first;
                            col = p.second;
                            step[row][col] = step[xx][yy]+1;
                        }
                    }
                    q.push({row,col});
                }
        }
    }
    for(int i=1 ; i<=n ; i++)
    {
        for(int j=1 ; j<=m ; j++)
            cout<<maze[i][j]<<" ";
        cout<<endl;
    }
    return -1;
}
int main()
{
    int st_x,st_y;
    cin>>n>>m;
    for(int i=1 ; i<=n ; i++)
        for(int j=1 ; j<=m ; j++)
        {
            cin>>maze[i][j];
            if(maze[i][j] == '@')
            {
                st_x=i; st_y=j;                
            }
        } 
    cout<<bfs(st_x,st_y)<<endl;
    return 0;    
}

2023/8/27 10:54
加载中...