글 읽기 - 탈옥 질문입니다.

joungho512 6년 전 0

임의로 죄수 1, 죄수2 큐2개를 나누어서

죄수1이 먼저 1칸씩 이동하고 바로 죄수 2가 1칸을 이동해서

둘다 탈출했을때 열고갔던 문의 최소 개수를 출력하는 식으로 했는데

알고리즘 자체가 틀린건지 잘 모르겠습니다.

#include <stdio.h>
#include <queue>

using namespace std;
queue<int> qc1,qc2;
queue<pair<int,int>> q1,q2;
int n,m;
char map[111][111];

int xd[4]={1,0,-1,0};
int yd[4]={0,1,0,-1};
bool v1[111][111];
bool v2[111][111];
bool d[111][111];
bool ck;

int bfs()
{
	int res1=987654321;
	int res2=987654321;
	int res= 987654321;

	while( !(q1.empty() && q2.empty()))
	{
		int q1_sz=q1.size();
		//printf("q1_sz%d\n",q1_sz);
		while( q1_sz--)
		{
			int ny,nx,nc;
			ny = q1.front().first;
			nx = q1.front().second;
			nc = qc1.front();
			q1.pop(); qc1.pop();
			//printf("1 ny%d nx%d nc%d\n",ny,nx,nc);
			
			if( ny <1 || nx <1 || ny >n || nx >m )
			{
				//printf("LAST 1 ny%d nx%d nc%d\n",ny,nx,nc);
				res1=nc;
				continue;
			}
			int ney,nex,nec;
			for(int i=0;i<4;i++)
			{
				ney = ny+yd[i];
				nex = nx+xd[i];
				if( v1[ney][nex]) continue;
				if( map[ney][nex] !='*') // 벽이 아니면
				{
					if(map[ney][nex] == '#')
					{
						nec=nc+1;
						d[ney][nex]=1;
						q1.push(make_pair(ney,nex));
						qc1.push(nec);
						v1[ney][nex]=1;
						//printf("1 ney%d nex%d nec%d\n",ney,nex,nec);
					}
					else
					{
						q1.push(make_pair(ney,nex));
						qc1.push(nc);
						v1[ney][nex]=1;
						//printf("1 ney%d nex%d nc%d\n",ney,nex,nc);
					}
				}
			}
		} //q1sz
		
		int q2_sz=q2.size();
		//printf("q2_sz%d\n",q2_sz);
		while( q2_sz--)
		{
			int ny,nx,nc;
			ny = q2.front().first;
			nx = q2.front().second;
			nc = qc2.front();
			q2.pop(); qc2.pop();
			//printf("2 ny%d nx%d nc%d\n",ny,nx,nc);
			if( ny <1 || nx <1 || ny >n || nx >m )
			{
				//printf("LAST 2 ny%d nx%d nc%d\n",ny,nx,nc);
				res2= nc;
				continue;
			}
			int ney,nex,nec;
			for(int i=0;i<4;i++)
			{
				ney = ny+yd[i];
				nex = nx+xd[i];
				if( v2[ney][nex]) continue;
				if( map[ney][nex] !='*') // 벽이 아니면
				{
					if(map[ney][nex] == '#')
					{
						nec=nc;
						if(!d[ney][nex]) nec=nc+1;
						
						q2.push(make_pair(ney,nex));
						qc2.push(nec);
						v2[ney][nex]=1;
						//printf("2 ney%d nex%d nec%d\n",ney,nex,nec);
					}
					else
					{
						q2.push(make_pair(ney,nex));
						qc2.push(nc);
						v2[ney][nex]=1;
						//printf("2 ney%d nex%d nc%d\n",ney,nex,nc);
					}
				}
			}
		} //q2sz

		//printf("res1 %d res2 %d\n",res1,res2);
		if( res > res1+res2) res= res1+res2;	
	}//q1empty

	
	return res;
}

void init()
{
	for(int i=0;i<=n+1;i++)
	{
		for(int j=0;j<=m+1;j++)
		{
			map[i][j]=NULL;
			v1[i][j]=0;
			v2[i][j]=0;
			d[i][j]=0;
		}
	}
	
	ck=0;
}


int main(void)
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d %d",&n,&m);

		for(int i=1;i<=n;i++)
		{
			for(int j=1; j<=m;j++)
			{
				scanf(" %1c",&map[i][j]);
				if( map[i][j] == '$' &&ck ==0)
				{
					q1.push(make_pair(i,j));
					qc1.push(0);
					//printf("1s ny%d nx%d nc%d\n",i,j,0);
					v1[i][j]=1;
					ck=1;
				}
				else if(map[i][j] == '$')
				{
					q2.push(make_pair(i,j));
					qc2.push(0);
					//printf("2s ny%d nx%d nc%d\n",i,j,0);
					v2[i][j]=1;
				}
			}
		}
		printf("%d\n",bfs());
		init();
	}

	
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

탈옥 질문입니다.

joungho512 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말