WA 66 pts 求条
查看原帖
WA 66 pts 求条
1235038
Ekin123楼主2025/8/30 13:43
#include <iostream>
#include <list>
#include <cstring>
using namespace std;

int n,m;

struct node
{
    int x,y;
};

char c[505][505];

int dis[505][505];

int dx[] = {-1,1,1,-1};
int dy[] = {-1,1,-1,1};
int cx[] = {1,0,0,1};
int cy[] = {1,0,1,0};
char check[] = {'\\','\\','/','/'};

int bfs(int sx,int sy)
{
    list<node> q;
    memset(dis,-1,sizeof dis);
    q.push_front({sx,sy});
    dis[sx][sy] = 0;
    while(!q.empty())
    {
        int x = q.front().x;
        int y = q.front().y;
        q.pop_front();
        if(x == n && y == m) return dis[x][y];
        for(int i = 0;i <= 3;i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            int checkx = nx + cx[i];
            int checky = ny + cy[i];
            if(0 <= nx && nx <= n && 0 <= ny && ny <= m && 
            0 <= checkx && checkx <= n && 0 <= checky && checky <= m && 
            dis[nx][ny] == -1)
            {
                if(c[checkx][checky] == check[i])
                {
                    dis[nx][ny] = dis[x][y];
                    q.push_front({nx,ny});
                }
                else
                {
                    dis[nx][ny] = dis[x][y] + 1;
                    q.push_back({nx,ny});
                }
            }
        }
    }
    return -1;
}

int main()
{
    cin >> n >> m;
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= m;j++)
        {
            cin >> c[i][j];
        }
    }
    int res = bfs(0,0);
    if(res == -1) cout << "NO SOLUTION" << endl;
    else cout << res << endl;
    return 0;
}
2025/8/30 13:43
加载中...