Submission #1080782

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080782		TrinhKhanhDung	Maze (JOI23_ho_t3)	C++14	8 / 100	175 ms	36764 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<bool>> vis;
vector<vector<int>> d;

void solve(){
    cin >> N >> M >> L;
    cin >> sx >> sy >> tx >> ty;
    a.resize(N + 3, vector<char>(M + 3, 0));
    vis.resize(N + 3, vector<bool>(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[2];
    
    if(a[sx][sy] != '#'){
        q[0].push({sx, sy});
        d[sx][sy] = 0;
        vis[sx][sy] = true;
    }
    else{
        for(int i=1; i<=N; i++){
            for(int j=1; j<=M; j++){
                if(abs(sx - i) <= L && abs(sy - j) <= L && abs(sx - i) + abs(sy - j) < 2 * L){
                    q[0].push({i, j});
                    d[i][j] = 1;
                    vis[i][j] = true;
                }
            }
        }
    }
    for(int t=0;; t++){
        int i = t & 1;
        vector<pair<int, int>> pos;
        while(sz(q[i])){
            int x = q[i].front().fi;
            int y = q[i].front().se;
            pos.push_back({x, y});
            q[i].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 || a[nx][ny] == '#' || vis[nx][ny]) continue;
                if(minimize(d[nx][ny], d[x][y])){
                    q[i].push({nx, ny});
                    vis[nx][ny] = true;
                }
            }
        }
        for(auto o: pos){
            queue<pair<int, int>> qq;
            qq.push({o.fi, o.se});
            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 < max(1, o.fi - L) || nx > min(N, o.fi + L) || ny < max(1, o.se - L) 
                        || ny > min(M, o.se + L) || vis[nx][ny]) continue;
                    if(abs(o.fi - nx) + abs(o.se - ny) >= 2 * L) continue;
                    if(minimize(d[nx][ny], d[o.fi][o.se] + 1)){
                        q[!i].push({nx, ny});
                        qq.push({nx, ny});
                        vis[nx][ny] = true;
                    }
                }
            }
        }
        if(vis[tx][ty]) 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: 0 / 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