16pts求条
查看原帖
16pts求条
911026
jaspersgr114514楼主2025/1/23 22:01
#include <bits/stdc++.h>
#define to first
#define w second
using namespace std;
int n, m;
const int N = 250005;
int dis[N], ans[N];
bool vis[N];
vector<int> v[N];
struct node
{
    int id, dis;
    bool operator<(const node &a) const
    {
        return dis > a.dis;
    }
};
priority_queue<node> q;
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            char c;
            cin >> c;
            if (c == '/')
            {
                v[n * (i - 1) + j + 1].push_back(n * i + j);
                v[n * i + j].push_back(n * (i - 1) + j + 1);
                v[n * (i - 1) + j].push_back(n * i + j + 1);
                v[n * i + j + 1].push_back(n * (i - 1) + j);
                dis[n * (i - 1) + j + 1] = 0;
                dis[n * i + j] = 0;
                dis[n * (i - 1) + j] = 1;
                dis[n * i + j + 1] = 1;
            }
            else
            {
                v[n * (i - 1) + j + 1].push_back(n * i + j);
                v[n * i + j].push_back(n * (i - 1) + j + 1);
                v[n * (i - 1) + j].push_back(n * i + j + 1);
                v[n * i + j + 1].push_back(n * (i - 1) + j);
                dis[n * (i - 1) + j + 1] = 1;
                dis[n * i + j] = 1;
                dis[n * (i - 1) + j] = 0;
                dis[n * i + j + 1] = 0;
            }
        }
    }
    q.push({1, 0});
    dis[1] = 0;
    ans[1] = 1;
    while (!q.empty())
    {
        int now = q.top().id;
        q.pop();
        if (vis[now])
        {
            continue;
        }
        vis[now] = 1;
        int sz = v[now].size();
        for (auto s : v[now])
        {
            if (dis[s] > dis[now] + 1)
            {
                dis[s] = dis[now] + 1;
                ans[s] = ans[now];
                q.push({s, dis[s]});
            }
            else if (dis[s] == dis[now] + 1)
            {
                ans[s] += ans[now];
            }
        }
    }
    cout << ans[n * n] << endl;
}
2025/1/23 22:01
加载中...