Submission #14552

#	Time	Username	Problem	Language	Result	Execution time	Memory
14552		jackae98	물병 (JOI14_bottle)	C++98	0 / 100	4197 ms	1968 KiB

bottle

#include <stdio.h>
#include <queue>
int h,w,p,q;
int s,t; 
struct Coor2{
	int x,y;
	int dis;
};
struct Coor{
	int x,y;
}b[210];
char a[210][210];
int dis[210][210];
int visit[210][210];
int dx[4] = {0,-1,0,1};
int dy[4] = {-1,0,1,0};
int max(int a,int b)
{
	return a>b?a:b;
}
void g(){
	for(int k=1;k<=p;k++){
		for(int i=1;i<=p;i++){
			for(int j=1;j<=p;j++){
				if(max(dis[i][k],dis[k][j]) < dis[i][j]){
					dis[i][j] = max(dis[i][k],dis[k][j]);
				}
			}
		}
	}
}
int getDis(int st,int ed){
	std::queue<Coor2> Q;
	int ex = b[ed].x;
	int ey = b[ed].y;
	Coor2 init;
	init.x = b[st].x;
	init.y = b[st].y;
	init.dis = 0;
	Q.push(init);
	while(!Q.empty()){
		Coor2 cur = Q.front();
		Q.pop();
		if(cur.x==ex&&cur.y==ey){
			return cur.dis;
		}
		for(int i=0;i<4;i++){
			if(cur.x+dx[i]>=0 && cur.x+dx[i]<h && cur.y+dy[i]>=0 && cur.y+dy[i]<w && a[cur.x+dx[i]][cur.y+dy[i]] == '.'&&visit[cur.x+dx[i]][cur.y+dy[i]] != st*p+ed){
				Coor2 next;
				next.x = cur.x+dx[i];
				next.y = cur.y+dy[i];
				visit[next.x][next.y] = st*p+ed;
				if(next.x==ex&&next.y==ey){
					return cur.dis;
				}
				next.dis = cur.dis+1;
				Q.push(next);
			}
		}
	}
	return 987654321;
}
void preinit(){
	for(int i=1;i<=p;i++){
		for(int j=i+1;j<=p;j++){
			dis[i][j] = getDis(i,j);
		}
	}
}
int main()
{
	scanf("%d %d %d %d",&h,&w,&p,&q);
	if(p>=210){
		printf("Cutting"); 
		return 0;
	}
	for(int i=0;i<h;i++){
		scanf("%s",a[i]);
	}
	for(int i=1;i<=p;i++){
		int x,y;
		scanf("%d %d",&x,&y);
		b[i].x = x-1;
		b[i].y = y-1;
	}
	preinit();
	g();
	for(int i=1;i<=q;i++){
		scanf("%d %d",&s,&t);
		if(dis[s][t]==987654321) printf("-1\n");
		else printf("%d\n",dis[s][t]);
	}
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30