Submission #16001

#	Time	Username	Problem	Language	Result	Execution time	Memory
16001		tonyjjw	Portals (BOI14_portals)	C++14	39 / 100	995 ms	190076 KiB

portals

//*
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<queue>
#define MN 1000
#define pb push_back
#pragma warning(disable:4996)
using namespace std;

int N,M;
char map[MN+2][MN+3];

struct PAIR{
	int x,y;
	PAIR(){}
	PAIR(int x_,int y_){
		x=x_,y=y_;
	}
	PAIR operator +(PAIR A)const{
		return PAIR(x+A.x,y+A.y);
	}
};

PAIR mp(int x,int y){
	return PAIR(x,y);
}

PAIR left[MN+2][MN+2],right[MN+2][MN+2],up[MN+2][MN+2],down[MN+2][MN+2],st,ed;
vector<PAIR> dir;
int wall_dist[MN+2][MN+2],visit[MN+2][MN+2],dist[MN+2][MN+2];
vector<PAIR> E[MN+2][MN+2];
vector<int> C[MN+2][MN+2];

int hsize;
struct HEAP{
	PAIR p;
	int d;
	HEAP(){}
	HEAP(PAIR p_,int d_){
		p=p_,d=d_;
	}
	bool operator <(HEAP A)const{
		return d>A.d;
	}
}H[MN*MN];

void push(PAIR p,int d){
	H[hsize++]=HEAP(p,d);
	push_heap(H,H+hsize);
}
void pop(){
	pop_heap(H,H+hsize);
	hsize--;
}

bool wall_check(PAIR a){
	return map[a.x][a.y]=='#';
}

int main(){
	dir.pb(mp(0,1)),dir.pb(mp(0,-1)),dir.pb(mp(1,0)),dir.pb(mp(-1,0));

//	freopen("input.txt","r",stdin),freopen("output.txt","w",stdout);
	scanf("%d%d",&N,&M);
	for(int i=0;i<=N+1;i++)for(int j=0;j<=M+1;j++)map[i][j]='#';
	for(int i=1;i<=N;i++)scanf("%s",map[i]+1);
	for(int i=1;i<=N;i++)map[i][M+1]='#';
	for(int i=1;i<=N;i++)for(int j=1;j<=M;j++){
		if(map[i][j]=='S')st=mp(i,j);
		if(map[i][j]=='C')ed=mp(i,j);
	}
	for(int i=1;i<=N;i++)for(int j=1;j<=M;j++){
		left[i][j]=(map[i][j-1]=='#')?mp(i,j):left[i][j-1];
		up[i][j]=(map[i-1][j]=='#')?mp(i,j):up[i-1][j];
	}
	for(int i=N;i>=1;i--)for(int j=M;j>=1;j--){
		right[i][j]=(map[i][j+1]=='#')?mp(i,j):right[i][j+1];
		down[i][j]=(map[i+1][j]=='#')?mp(i,j):down[i+1][j];
	}

	queue<PAIR> que;
	for(int i=0;i<=N+1;i++)for(int j=0;j<=M+1;j++){
		if(map[i][j]=='#'){
			que.push(mp(i,j));
			visit[i][j]=1;
		}
	}
	while(!que.empty()){
		auto h=que.front(); que.pop();
		for(auto d:dir){
			auto next=h+d;
			if(next.x<0 || next.x>N+1 || next.y<0 || next.y>M+1)continue;
			if(visit[next.x][next.y] || map[next.x][next.y]=='#')continue;
			visit[next.x][next.y]=1;
			wall_dist[next.x][next.y]=wall_dist[h.x][h.y]+1;
			que.push(next);
		}
	}
	for(int i=1;i<=N;i++)for(int j=1;j<=M;j++){
		if(wall_check(mp(i,j)))continue;
		if(!wall_check(left[i][j])){
			E[i][j].pb(left[i][j]);
			C[i][j].pb(wall_dist[i][j]);
		}
		if(!wall_check(right[i][j])){
			E[i][j].pb(right[i][j]);
			C[i][j].pb(wall_dist[i][j]);
		}
		if(!wall_check(up[i][j])){
			E[i][j].pb(up[i][j]);
			C[i][j].pb(wall_dist[i][j]);
		}
		if(!wall_check(down[i][j])){
			E[i][j].pb(down[i][j]);
			C[i][j].pb(wall_dist[i][j]);
		}
		for(auto d:dir){
			if(!wall_check(mp(i,j)+d)){
				E[i][j].pb(mp(i,j)+d);
				C[i][j].pb(1);
			}
		}
	}
	for(int i=1;i<=N;i++)for(int j=1;j<=M;j++){
		visit[i][j]=0;
		dist[i][j]=1e9;
	}

	push(st,0);
	while(hsize){
		auto top=H[0];
		pop();
		if(visit[top.p.x][top.p.y])continue;
		visit[top.p.x][top.p.y]=1;
		dist[top.p.x][top.p.y]=top.d;
		for(int i=0;i<E[top.p.x][top.p.y].size();i++){
			auto t=E[top.p.x][top.p.y][i];
			auto c=C[top.p.x][top.p.y][i];
			push(t,top.d+c);
		}
	}
	printf("%d",dist[ed.x][ed.y]);

	return 0;
}
//*/

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