Submission #6921

#	Time	Username	Problem	Language	Result	Execution time	Memory
6921		tncks0121	Portals (BOI14_portals)	C++98	100 / 100	368 ms	31372 KiB

portals

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <deque>
#include <utility>
#include <bitset>
#include <limits.h>

using namespace std;
typedef long long ll;
typedef unsigned long long llu;
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;

const int SZ = 1005;

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

int R, C;
char D[SZ][SZ];

queue<int> que;
void ins (int x, int y) {
    que.push(x);
    que.push(y);
}

int dist_wall[SZ][SZ];
int where_portal[4][SZ][SZ];

struct state {
    int x, y, d;
    state (int x = 0, int y = 0, int d = 0): x(x), y(y), d(d) { }
    bool operator < (const state &s) const { return d < s.d; }
    bool operator > (const state &s) const { return d > s.d; }
};

priority_queue<state, vector<state>, greater<state> > PQ;
int dst[SZ][SZ];

int main() {
    scanf("%d%d", &R, &C);
    for(int i = 1; i <= R; i++) scanf("%s", D[i]+1);
    
    // step 1: 각 격자에서 벽까지의 거리 구하기
    for(int i = 1; i <= R; i++) ins(i, 0), ins(i, C+1), D[i][0] = D[i][C+1] = '#';
    for(int j = 1; j <= C; j++) ins(0, j), ins(R+1, j), D[0][j] = D[R+1][j] = '#';
    for(int i = 1; i <= R; i++) for(int j = 1; j <= C; j++) {
        dst[i][j] = (int)1e6;
        if(D[i][j] == '#') que.push(i), que.push(j);
        if(D[i][j] == 'S') PQ.push( state(i, j, 0) ), dst[i][j] = 0;
    }
    
    while(!que.empty()) {
        int x = que.front(); que.pop();
        int y = que.front(); que.pop();
        for(int d = 0; d < 4; d++) {
            int xx = x+dx[d], yy = y+dy[d];
            if(D[xx][yy] == '#') continue;
            if(xx < 1 || yy < 1 || xx > R || yy > C || dist_wall[xx][yy] > 0) continue;
            dist_wall[xx][yy] = dist_wall[x][y] + 1;
            que.push(xx); que.push(yy);
        }
    }
    
    // step 2: 각 격자에서 위, 아래, 오른쪽, 왼쪽으로 포탈 쏘았을 때 닿는 벽 구하기
    for(int i = 1; i <= R; i++) {
        for(int j = 1; j <= C; j++) {
            where_portal[0][i][j] = (D[i-1][j] == '#') ? i : where_portal[0][i-1][j];
            where_portal[2][i][j] = (D[i][j-1] == '#') ? j : where_portal[2][i][j-1];
        }
    }
    for(int i = R; i > 0; i--) {
        for(int j = C; j > 0; j--) {
            where_portal[1][i][j] = (D[i+1][j] == '#') ? i : where_portal[1][i+1][j];
            where_portal[3][i][j] = (D[i][j+1] == '#') ? j : where_portal[3][i][j+1];
        }
    }
    
    // step 3: dijkstra
    while(!PQ.empty()) {
        state s = PQ.top(); PQ.pop();
        if(s.d > dst[s.x][s.y]) continue;
        if(D[s.x][s.y] == 'C') {
            printf("%d\n", s.d);
            return 0;
        }
        for(int d = 0; d < 4; d++) {
            state nxt = state(s.x + dx[d], s.y + dy[d], s.d + 1);
            if(D[nxt.x][nxt.y] == '#') continue;
            if(nxt.x < 1 || nxt.y < 1 || nxt.x > R || nxt.y > C) continue;
            if(dst[nxt.x][nxt.y] > nxt.d) {
                dst[nxt.x][nxt.y] = nxt.d;
                PQ.push (nxt);
            }
        }
        for(int d = 0; d < 4; d++) {
            state nxt = (d < 2) ?
                state(where_portal[d][s.x][s.y], s.y, s.d + dist_wall[s.x][s.y])
                : state(s.x, where_portal[d][s.x][s.y], s.d + dist_wall[s.x][s.y]);
            if(D[nxt.x][nxt.y] == '#') continue;
            if(nxt.x < 1 || nxt.y < 1 || nxt.x > R || nxt.y > C) continue;
            if(dst[nxt.x][nxt.y] > nxt.d) {
                dst[nxt.x][nxt.y] = nxt.d;
                PQ.push (nxt);
            }
        }
    }
    
    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 19 / 19
• Subtask 5: 30 / 30