Submission #1291168

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291168		nguyenkhangninh99	Two Currencies (JOI23_currencies)	C++20	0 / 100	1 ms	572 KiB

currencies

#include <bits/stdc++.h>
using namespace std;

const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};
int r, c, k; 

bool inside(int x, int y){
    return (1 <= x && x <= r && 1 <= y && y <= c);
}
void solve(){   
    cin >> r >> c >> k;

    vector<vector<int>> d(r + 1, vector<int>(c + 1, -1));
    vector<vector<int>> cell(r + 1, vector<int>(c + 1, 0));
    vector<vector<int>> vis(r + 1, vector<int>(c + 1, 0));
    int sx, sy, tx, ty; cin >> sx >> sy >> tx >> ty;

    for(int i = 1; i <= r; i++){
        for(int j = 1; j <= c; j++){
            char x; cin >> x;
            if(x == '#') cell[i][j] = 1;
        }
    }

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

    while(q.size()){
        auto [x, y] = q.front();
        q.pop_front();
        if(vis[x][y]) continue;
        vis[x][y] = 1;
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i], ny = y + dy[i];
            if(inside(nx, ny)){
                if(!cell[nx][ny] && (d[nx][ny] == -1 || (d[nx][ny] > d[x][y]))){
                    q.push_front({nx, ny});
                    d[nx][ny] = d[x][y];
                }
            }
        }

        for(int nny: {y - k, y + k}){
            if(1 <= nny && nny <= c){
                int lbound = max(1, x - (k - 1));
                int rbound = min(r, x + (k - 1));
                for(int nnx = lbound; nnx <= rbound; nnx++){
                    if(d[nnx][nny] == -1 || (d[nnx][nny] > d[x][y] + 1)){
                        q.push_back({nnx, nny});
                        d[nnx][nny] = d[x][y] + 1;
                    }
                }
            }
        }

        for(int nnx: {x - k, x + k}){
            if(1 <= nnx && nnx <= r){
                int lbound = max(1, y - (k - 1));
                int rbound = min(c, y + (k - 1));
                for(int nny = lbound; nny <= rbound; nny++){
                    if(d[nnx][nny] == -1 || (d[nnx][nny] > d[x][y] + 1)){
                        q.push_back({nnx, nny});
                        d[nnx][nny] = d[x][y] + 1;
                    }
                }
            }
        }

        if(abs(tx - x) <= k && abs(ty - y) <= k){
            if(abs(tx - x) == k && abs(ty - y) == k) continue;
            if(d[tx][ty] == -1 || (d[tx][ty] > d[x][y] + 1)){
                q.push_back({tx, ty});
                d[tx][ty] = d[x][y] + 1;
            }
        }
    }
    cout << d[tx][ty];
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    solve();
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 28
• Subtask 3: 0 / 30
• Subtask 4: 0 / 32