oj.uz

Submission #298595

# Submission time Handle Problem Language Result Execution time Memory
298595 2020-09-13T11:18:06 Z shrek12357 Portal (COCI17_portal) C++14
120 / 120
 73 ms 21024 KB 
#include<bits/stdc++.h>
using namespace std;
 
 
const int N = 1005,
          INF = 1e9,
          dx[] = {-1, 0, 1, 0},
          dy[] = {0, -1, 0, 1};
 
 
int n, m;
char a[N][N];
int dist_to_wall[N][N], d[N][N];
int sx, sy, tx, ty;
pair < int, int > nxt[4][N][N];
 
inline bool is_wall(int x, int y){
    return x < 1 || x > n || y < 1 || y > m || a[x][y] == '#';
}
 
void walls(){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            dist_to_wall[i][j] = INF;
        }
    }
    queue < pair < int, int > > q;
    for(int i = 0; i <= n + 1; i++){
        for(int j = 0; j <= m + 1; j++){
            if(is_wall(i, j)){
                dist_to_wall[i][j] = 0;
                q.push(make_pair(i, j));
            }
        }
    }
    while(!q.empty()){
        int x = q.front().first,
            y = q.front().second;
        q.pop();
        for(int i = 0; i < 4; i++){
            int xx = x + dx[i],
                yy = y + dy[i];
            if(is_wall(xx, yy)){
                continue;
            }
            if(dist_to_wall[xx][yy] > dist_to_wall[x][y] + 1){
                dist_to_wall[xx][yy] = dist_to_wall[x][y] + 1;
                q.push(make_pair(xx, yy));
            }
        }
    }
}
 
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> a[i][j];
        }
    }
    walls();
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(j == 1 || a[i][j - 1] == '#'){
                nxt[0][i][j] = make_pair(i, j);
            }
            else{
                nxt[0][i][j] = nxt[0][i][j - 1];
            }
            if(i == 1 || a[i - 1][j] == '#'){
                nxt[1][i][j] = make_pair(i, j);
            }
            else{
                nxt[1][i][j] = nxt[1][i - 1][j];
            }
        }
    }
    for(int i = n; i >= 1; i--){
        for(int j = m; j >= 1; j--){
            if(j == m || a[i][j + 1] == '#'){
                nxt[2][i][j] = make_pair(i, j);
            }
            else{
                nxt[2][i][j] = nxt[2][i][j + 1];
            }
            if(i == n || a[i + 1][j] == '#'){
                nxt[3][i][j] = make_pair(i, j);
            }
            else{
                nxt[3][i][j] = nxt[3][i + 1][j];
            }
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            d[i][j] = INF;
            if(a[i][j] == 'C'){
                sx = i;
                sy = j;
            }
            else if(a[i][j] == 'F'){
                tx = i;
                ty = j;
            }
        }
    }
    priority_queue < pair < int, pair < int, int > > > q;
    d[sx][sy] = 0;
    q.push(make_pair(0, make_pair(sx, sy)));
    while(!q.empty()){
        int val = -q.top().first,
            x = q.top().second.first,
            y = q.top().second.second;
        q.pop();
        if(d[x][y] < val){
            continue;
        }
        for(int i = 0; i < 4; i++){
            int xx = x + dx[i],
                yy = y + dy[i];
            if(!is_wall(xx, yy) && d[xx][yy] > d[x][y] + 1){
                d[xx][yy] = d[x][y] + 1;
                q.push(make_pair(-d[xx][yy], make_pair(xx, yy)));
            }
        }
        for(int i = 0; i < 4; i++){
            int xx = nxt[i][x][y].first,
                yy = nxt[i][x][y].second;
            if(d[xx][yy] > d[x][y] + dist_to_wall[x][y]){
                d[xx][yy] = d[x][y] + dist_to_wall[x][y];
                q.push(make_pair(-d[xx][yy], make_pair(xx, yy)));
            }
        }
    }
    if(d[tx][ty] == INF){
        return cout << "nemoguce", 0;
    }
    cout << d[tx][ty];
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 768 KB Output is correct
2 Correct 1 ms 768 KB Output is correct
3 Correct 1 ms 768 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6016 KB Output is correct
2 Correct 4 ms 3584 KB Output is correct
3 Correct 6 ms 3712 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 6248 KB Output is correct
2 Correct 8 ms 7120 KB Output is correct
3 Correct 8 ms 4588 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 14764 KB Output is correct
2 Correct 29 ms 10248 KB Output is correct
3 Correct 21 ms 10892 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 18528 KB Output is correct
2 Correct 28 ms 19468 KB Output is correct
3 Correct 32 ms 12700 KB Output is correct
4 Correct 28 ms 14356 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 21024 KB Output is correct
2 Correct 33 ms 20864 KB Output is correct
3 Correct 48 ms 20768 KB Output is correct
4 Correct 50 ms 20888 KB Output is correct