MazeConstruct.cpp

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
using P = pair<int, int>;
using ll = long long;

struct MazeConstruct {
    vector<string> construct(int k) {
        if(k+1 <= 50) return vector<string>(1, string(k+1, '.'));
        if(k <= 100-2) return vector<string>(50, string(k+1-49, '.'));
        int H = 50, W = 50;
        if(k % 2 == 1){
            W--;
        }
        vector<string> ans(H, string(W, '.'));
        k -= H + W - 2;
        for(int i=0;i<H-1;i++){
            ans[i][W-1] = '#';
        }

        int j = W - 3;
        while(k > 0){
            int top_height;
            if(k > (H-1) * 2){
                top_height = H - 1;
                k -= (H-1) * 2;
            }else{
                top_height = k / 2;
                k = 0;
            }
            for(int i=0;i<top_height;i++){
                ans[H-1-i][j] = '#';
            }
            for(int i=0;i<H-1;i++){
                ans[i][j-2] = '#';
            }
            j -= 4;
        }

        return ans;
    }
};

int minDist[52][52];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

int main(){
    MazeConstruct mc;
    for(int k=1;k<=1000;k++){
        vector<string> field = mc.construct(k);

        memset(minDist, -1, sizeof(minDist));
        queue<P> que;
        que.emplace(0, 0);
        minDist[0][0] = 0;
        bool checked = false;
        while(que.size()){
            P p = que.front(); que.pop();
            int y = p.first, x = p.second;
            if(y == field.size()-1 && x == field[0].size()-1){
                assert(minDist[y][x] == k);
                checked = true;
                break;
            }
            for(int i=0;i<4;i++){
                int ny = y + dy[i], nx = x + dx[i];
                if(ny < 0 || field.size() <= ny || nx < 0 || field[0].size() <= nx || field[ny][nx] == '#') continue;
                if(minDist[ny][nx] == -1 || minDist[ny][nx] > minDist[y][x]+1){
                    minDist[ny][nx] = minDist[y][x]+1;
                    que.emplace(ny, nx);
                }
            }
        }
        assert(checked);
    }

    return 0;
}