Submission #735609

#	Time	Username	Problem	Language	Result	Execution time	Memory
735609		josanneo22	Portals (BOI14_portals)	C++17	70 / 100	1086 ms	146196 KiB

portals

#include<bits/stdc++.h>
using namespace std;
 
#define int long long
#define mp make_pair
#define fi first
#define se second

const int maxn=1005;
int a[maxn][maxn],ans[maxn][maxn],up[maxn][maxn],dw[maxn][maxn],rt[maxn][maxn],lf[maxn][maxn];
int n,m,sx,sy,ex,ey;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

struct e{
	int x,y,dist;
};
class comp {
public:
    bool operator()(e f,e s)
    {
		return f.dist>s.dist;
    }
};
bool valid(int x,int y){
	if(x>=0 && x<=n-1 && y>=0 && y<=m-1 && a[x][y]==1) return true;
	else return false;
}
void init(){
	for (int i=0; i<n; i++)  
        for (int j=0; j<m; j++) 
			ans[i][j]=1e9;
	for (int i=0; i<n; i++) {
        int pre = 0;
        for (int j=0; j<m; j++) {
            if(a[i][j]==0) pre = j+1;
            lf[i][j] = pre;
        }
    }
    for (int i=0; i<n; i++) {
        int pre = m-1;
        for (int j=m-1; j>=0; j--) {
            if(a[i][j] ==0) pre = j-1;
            rt[i][j] = pre;
        }
    }
    for (int j=0; j<m; j++) {
        int pre = 0;
        for (int i=0; i<n; i++) {
            if(a[i][j] == 0) pre = i+1;
            up[i][j] = pre;
        }
    }
    for (int j=0; j<m; j++) {
        int pre = n-1;
        for (int i=n-1; i>=0; i--) {
            if(a[i][j] == 0) pre = i-1;
            dw[i][j] = pre;
        }
    }
}
signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>n>>m;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			char x; cin>>x;
			if(x=='#') a[i][j]=0;
			else a[i][j]=1;

			if(x=='S') {sx=i;sy=j;}
			if(x=='C') {ex=i;ey=j;}
		}
	}
	init();
	priority_queue<e,vector<e>,comp> pq;
	pq.push({sx,sy,0});
	while(pq.size()){
		e u=pq.top(); pq.pop();
		if(ans[u.x][u.y]<=u.dist) continue;
		if(u.x==ex && u.y==ey){
			cout<<u.dist<<'\n';
			return 0;
		}
		ans[u.x][u.y]=u.dist;
		for(int i=0;i<4;i++){
			if(valid(u.x+dx[i],u.y+dy[i])) 
			pq.push({u.x+dx[i],u.y+dy[i],u.dist+1});
		}
		//找到最靠近的传送门
		int mn=min({abs(u.x-up[u.x][u.y]),
					abs(u.x-dw[u.x][u.y]),
					abs(u.y-rt[u.x][u.y]),
					abs(u.y-lf[u.x][u.y])
				});
		//往上下左右发射，走mn个步就可以到那里然后tp就要+1
		if(valid(u.x,rt[u.x][u.y])) pq.push({u.x,rt[u.x][u.y],u.dist+mn+1});
		if(valid(u.x,lf[u.x][u.y])) pq.push({u.x,lf[u.x][u.y],u.dist+mn+1});
		if(valid(up[u.x][u.y],u.y)) pq.push({up[u.x][u.y],u.y,u.dist+mn+1});
		if(valid(dw[u.x][u.y],u.y)) pq.push({dw[u.x][u.y],u.y,u.dist+mn+1});
	}
}

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