Submission #340076

#	Time	Username	Problem	Language	Result	Execution time	Memory
340076		limabeans	Portals (BOI14_portals)	C++17	0 / 100	1 ms	620 KiB

portals

#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
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30