oj.uz

Submission #340076

# Submission time Handle Problem Language Result Execution time Memory
340076 2020-12-26T20:09:52 Z limabeans Portals (BOI14_portals) C++17
0 / 100
 1 ms 620 KB 
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 1010;
const int inf = 1e9;

int n, m;
string g[maxn];
int dp[maxn][maxn];

int dr[4]={0,0,1,-1};
int dc[4]={1,-1,0,0};

int L[maxn][maxn], R[maxn][maxn], U[maxn][maxn], D[maxn][maxn];

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

    cin>>n>>m;
    g[0] = string(m+2, '#');
    g[n+1] = string(m+2, '#');
    for (int i=1; i<=n; i++) {
	cin>>g[i];
	g[i]="#"+g[i]+"#";
    }
    
    for (int i=0; i<=n+1; i++) {
	for (int j=0; j<=m+1; j++) {
	    if (g[i][j]=='#') {
		L[i][j]=j;
		U[i][j]=i;
	    } else {
		L[i][j]=L[i][j-1];
		U[i][j]=U[i-1][j];
	    }
	}
	for (int j=m+1; j>=0; j--) {
	    if (g[i][j]=='#') {
		R[i][j]=j;
	    } else {
		R[i][j]=R[i][j+1];
	    }
	}
    }

    for (int i=n+1; i>=0; i--) {
	for (int j=0; j<=m+1; j++) {
	    if (g[i][j]=='#') {
		D[i][j]=i;
	    } else {
		D[i][j]=D[i+1][j];
	    }
	}
    }

    priority_queue<pair<int,pair<int,int>>> pq;

    for (int i=1; i<=n; i++) {
	for (int j=1; j<=m; j++) {
	    dp[i][j] = inf;
	    if (g[i][j]=='S') {
		dp[i][j] = 0;
		pq.push({-0, {i,j}});
	    }
	}
    }


    while (pq.size()) {
	auto cur = pq.top();
	pq.pop();
	int x = cur.second.first;
	int y = cur.second.second;
	if (-cur.first > dp[x][y]) {
	    continue;
	}
	for (int j=0; j<4; j++) {
	    int nx=x+dr[j];
	    int ny=y+dc[j];
	    if (g[nx][ny]=='#') {
		int tx=-1,ty=-1;
		if (nx==x+1 && ny==y) {
		    //down
		    tx=U[x][y]+1; ty=y;
		} else if (nx==x-1 && ny==y) {
		    //up
		    tx=D[x][y]-1; ty=y;
		} else if (nx==x && ny==y+1) {
		    //right
		    tx=x; ty=L[x][y]+1;
		} else if (nx==x && ny==y-1) {
		    //left
		    tx=x; ty=R[x][y]-1;
		} else assert(false);


		if (dp[tx][ty] > 1+dp[x][y]) {
		    dp[tx][ty]=1+dp[x][y];
		    pq.push({-dp[tx][ty],{tx,ty}});
		}
		
	    } else {
		if (dp[nx][ny] > 1+dp[x][y]) {
		    dp[nx][ny]=1+dp[x][y];
		    pq.push({-dp[nx][ny],{nx,ny}});
		}
	    }
	}
    }

    for (int i=1; i<=n; i++) {
	for (int j=1; j<=m; j++) {
	    if (g[i][j]=='C') {
		out(dp[i][j]);
	    }
	}
    }
    
    
    return 0;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Incorrect 1 ms 620 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Incorrect 1 ms 620 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Incorrect 1 ms 620 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Incorrect 1 ms 620 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 500 KB Output is correct
5 Incorrect 1 ms 620 KB Output isn't correct
6 Halted 0 ms 0 KB -