Submission #478595

#	Time	Username	Problem	Language	Result	Execution time	Memory
478595		sumit_kk10	물병 (JOI14_bottle)	C++17	0 / 100	5097 ms	53704 KiB

bottle

#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define ll long long int
#define ld long double
using namespace std;
const int N = 2005;
const int MOD = 1e9 + 7;
int n, m, p, q, ct, dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
int component[N][N], dis[N][N];
char a[N][N];
bool vis[N][N];
bool pos[N][N];
pair<int, int> houses[N];

bool check(int i, int j){
    return (i >= 1 and i <= n and j >= 1 and j <= m and a[i][j] != '#' and !vis[i][j]);
}

bool check1(int i, int j){
    return (i >= 1 and i <= n and j >= 1 and j <= m and a[i][j] != '#');
}

void dfs(int i, int j, int x){
    component[i][j] = x;
    vis[i][j] = true;
    for(int k = 0; k < 4; ++k){
        int _i = i + dx[k], _j = j + dy[k];
        if(check(_i, _j))
            dfs(_i, _j, x);
    }
}

void solve(){
    cin >> n >> m >> p >> q;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            component[i][j] = ct;
            ++ct;
        }
    }
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            cin >> a[i][j];
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            if(!vis[i][j])
                dfs(i, j, component[i][j]);
    for(int i = 1; i <= p; ++i){
        int u, v;
        cin >> u >> v;
        houses[i] = {u, v};
        pos[u][v] = true;
    }
    for(int i = 1; i <= q; ++i){
        int u, v;
        cin >> u >> v;
        if(component[houses[u].first][houses[u].second] != component[houses[v].first][houses[v].second]){
            cout << "-1\n";
            continue;
        }
        deque<pair<int, pair<int, pair<int, int> > > > q;
        q.push_back({0, {0, {houses[v].first, houses[v].second}}});
        for(int _i = 1; _i <= n; ++_i)
            for(int j = 1; j <= m; ++j)
                dis[_i][j] = INT_MAX;
        dis[houses[v].first][houses[v].second] = 0;
        int x = houses[u].first, y = houses[u].second;
        while(!q.empty()){
            int mx_cost = q.front().first, cost = q.front().second.first, _u = q.front().second.second.first, _v = q.front().second.second.second;
            q.pop_front();
            for(int k = 0; k < 4; ++k){
                int __u = _u + dx[k], __v = _v + dy[k];
                if(check1(__u, __v)){
                    if(pos[__u][__v] and dis[__u][__v] > max(mx_cost, cost + 1))
                        q.push_front({max(mx_cost, cost + 1), {0, {__u, __v}}});
                    else if(dis[__u][__v] > max(mx_cost, cost + 1))
                        q.push_back({max(mx_cost, cost + 1), {cost + 1, {__u, __v}}});
                    dis[__u][__v] = max(mx_cost, cost + 1);
                }
            }
        }
        cout << dis[x][y] - 1 << "\n";
    }
}

int main(){
    fast;
    int t = 1;
    // cin >> t;
    while(t--)
        solve();
    return 0;
}

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