Submission #1081846

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081846		TrinhKhanhDung	Maze (JOI23_ho_t3)	C++14	27 / 100	190 ms	35488 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define sz(x) (int)x.size()
#define ALL(v) v.begin(),v.end()
#define MASK(k) (1LL << (k))
#define BIT(x, i) (((x) >> (i)) & 1)
#define oo (ll)1e18
#define INF (ll)1e9
#define MOD (ll)(998244353)

using namespace std;

template<class T1, class T2>
    bool maximize(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}

template<class T1, class T2>
    bool minimize(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}

template<class T1, class T2>
    void add(T1 &a, T2 b){a += b; if(a >= MOD) a -= MOD;}

template<class T1, class T2>
    void sub(T1 &a, T2 b){a -= b; if(a < 0) a += MOD;}

template<class T>
    void cps(T &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}

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

int N, M, L;
int sx, sy, tx, ty;
vector<vector<char>> a;
vector<vector<int>> d;

void solve(){
    cin >> N >> M >> L;
    cin >> sx >> sy >> tx >> ty;
    a.resize(N + 3, vector<char>(M + 3, 0));
    d.resize(N + 3, vector<int>(M + 3, INF));
    for(int i=1; i<=N; i++){
        for(int j=1; j<=M; j++){
            cin >> a[i][j];
        }
    }

    queue<pair<int, int>> q;
    q.push({sx, sy});
    d[sx][sy] = 0;

    while(true){
        vector<pair<int, int>> pos;
        while(sz(q)){
            int x = q.front().fi;
            int y = q.front().se;
            q.pop();
            pos.push_back({x, y});
            for(int k=0; k<4; k++){
                int nx = x + dx[k], ny = y + dy[k];
                if(nx < 1 || nx > N || ny < 1 || ny > M || a[nx][ny] == '#') continue;
                if(minimize(d[nx][ny], d[x][y])){
                    q.push({nx, ny});
                }
            }
        }
        for(auto o: pos){
            queue<pair<int, int>> qq;
            qq.push({o.fi, o.se});
            if(o.fi > L && minimize(d[o.fi - L][o.se], d[o.fi][o.se] + 1)) qq.push({o.fi - L, o.se}), q.push({o.fi - L, o.se});
            if(o.se > L && minimize(d[o.fi][o.se - L], d[o.fi][o.se] + 1)) qq.push({o.fi, o.se - L}), q.push({o.fi, o.se - L});
            if(o.fi + L <= N && minimize(d[o.fi + L][o.se], d[o.fi][o.se] + 1)) qq.push({o.fi + L, o.se}), q.push({o.fi + L, o.se});
            if(o.se + L <= M && minimize(d[o.fi][o.se + L], d[o.fi][o.se] + 1)) qq.push({o.fi, o.se + L}), q.push({o.fi, o.se + L});
            while(sz(qq)){
                int x = qq.front().fi;
                int y = qq.front().se;
                qq.pop();
                for(int k=0; k<4; k++){
                    int nx = x + dx[k], ny = y + dy[k];
                    if(nx < 1 || nx > N || ny < 1 || ny > M) continue;
                    int t1 = abs(nx - o.fi), t2 = abs(ny - o.se);
                    if(t1 > L || t2 > L || t1 + t2 == 2 * L) continue;
                    if(d[o.fi - 1][o.se] == d[o.fi][o.se] && nx < o.fi) continue;
                    if(d[o.fi + 1][o.se] == d[o.fi][o.se] && nx > o.fi) continue;
                    if(d[o.fi][o.se - 1] == d[o.fi][o.se] && ny < o.se) continue;
                    if(d[o.fi][o.se + 1] == d[o.fi][o.se] && ny > o.se) continue;
                    if(minimize(d[nx][ny], d[o.fi][o.se] + 1)){
                        qq.push({nx, ny});
                        q.push({nx, ny});
                    }
                }
            }
        }
        if(d[tx][ty] < INF) break;
    }

    // for(int i=1; i<=N; i++){
    //     for(int j=1; j<=M; j++){
    //         cout << d[i][j] << ' ';
    //     }
    //     cout << '\n';
    // }
    cout << d[tx][ty] << '\n';
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    // freopen("flowers.inp", "r", stdin);
    // freopen("flowers.out", "w", stdout);

    int nTest = 1;

    while(nTest--)
        solve();

    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 19 / 19
• Subtask 3: 0 / 16
• Subtask 4: 0 / 19
• Subtask 5: 0 / 5
• Subtask 6: 0 / 19
• Subtask 7: 0 / 8
• Subtask 8: 0 / 6