玄关求助16pts7x
查看原帖
玄关求助16pts7x
923403
FallingFYC_楼主2024/7/12 08:46
#include <bits/stdc++.h>
using namespace std;
const int dx[] = {-1 , -1 , 1 , 1};
const int dy[] = {-1 , 1 , -1 , 1};
const int dirs[] = {2 , 1 , 1 , 2};
const int dsx[] = {-1 , -1 , 0 , 0};
const int dsy[] = {-1 , 0 , -1 , 0};
int n , m , g[505][505] , dis[505][505];
char c;
struct Node {int x , y , d;};
int main()
{
    cin >> n >> m;
    for (int i = 1 ; i <= n ; i++)
        for (int j = 1 ; j <= m ; j++)
        {
            while (c != '/' && c != '\\') c = getchar();
            g[i][j] = (c == '/' ? 1 : 2);
        }
    deque<Node> dq;
    dq.push_back({1 , 1 , 0});
    memset(dis , 0x3f , sizeof(dis));
    dis[1][1] = 0;
    while (!dq.empty())
    {
        Node now = dq.front();
        dq.pop_front();
        for (int i = 0 ; i < 4 ; i++)
        {
            int nx = now.x + dx[i] , ny = now.y + dy[i] , d = (g[now.x + dsx[i]][now.y + dsy[i]] != dirs[i]);
            if (nx >= 1 && ny >= 1 && nx <= n + 1 && ny <= m + 1 && dis[nx][ny] > dis[now.x][now.y] + d)
            {
                dis[nx][ny] = dis[now.x][now.y] + d;
                if (!d) dq.push_front({nx , ny , dis[nx][ny]});
                else dq.push_back({nx , ny , dis[nx][ny]});
            }
        }
    }
    if (dis[n + 1][m + 1] == 0x3f3f3f3f) cout << "NO SOLUTION";
    else cout << dis[n + 1][m + 1];
    return 0;
}
2024/7/12 08:46
加载中...