题解 | #走一个大整数迷宫#

将set换成unordered_set就过了； 红黑树并没那么高效；

解题过程

还是传统的bfs，只不过每一步多存了个value；然后将visited换为比较value；

void solve() {
    int n, m, p; cin >> n >> m >> p;
    vector<vector<int>> grid(n + 1, vector<int>(m + 1));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int x;
            cin >> x;
                grid[i][j]=x%(p-1);
        }
    }
    vector<pair<int, int>> direction = { {0,1},{1,0},{0,-1},{-1,0} };
    vector<vector<bool>> visited(n + 1, vector<bool>(m + 1));
    deque<dot> de;
    vector<vector<unordered_set<int>>> values(n + 1, vector<unordered_set<int>>(m + 1));
    de.push_back({ 1,1,grid[1][1] });
    values[1][1].insert(grid[1][1]);
    int ncount = 0;
    bool flag = 0;
    while (!de.empty()) {
        int s = de.size();
        for (int i = 0; i < s; i++) {
            dot d = de.front();
            de.pop_front();
            if (d.x == n && d.y == m && d.v % (p - 1) == 0) {
                flag = 1;
                break;
            }
            for (pair<int, int> direc : direction) {
                int x = d.x + direc.first;
                int y = d.y + direc.second;
                if (x == n && y == m && (d.v + grid[x][y]) % (p - 1) == 0) {
                    flag = 1;
                    ncount++;
                    break;
                }
                if (x<1 || x>n || y<1 || y>m)continue;
                if (values[x][y].find((d.v + grid[x][y]) % (p - 1)) != values[x][y].end())continue;
                values[x][y].insert((d.v + grid[x][y]) % (p - 1));
                de.push_back({ x,y,(d.v + grid[x][y])%(p-1)});
            }
            if (flag)break;
        }
        if (flag)break;
        ncount++;
    }
    cout << ncount;
}