글 읽기 - 2차원배열 2개와 4차원배열

wjavm2 4년 전 0

이 문제를 풀때 방문체크하는 배열을 red와 blue두개의 색깔별로 2차원배열 2개를생성해서 체크해준다음 풀면 왜 틀리고

두개를 합쳐서 사차원배열로 생성해서 방문체크를 해주면 맞을까요?????

#include<iostream>
#include<queue>

using namespace std;

int N, M;
char map[15][15] = { 0 };
struct marble { int rx, ry, bx, by, cnt; };
struct team { int red, blue; };
marble ma1;
int visit[15][15][15][15] = { 0 };
queue<marble>Q;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };

int BFS();

int main()
{
	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> map[i][j];
			if (map[i][j] == 'R')
			{
				ma1.rx = i; ma1.ry = j;
				map[i][j] = '.';
				
			}
			else if (map[i][j] == 'B')
			{
				ma1.bx = i; ma1.by = j;
				map[i][j] = '.';
			}
			
		}
	}
	
	Q.push({ ma1.rx,ma1.ry,ma1.bx,ma1.by,0 });
	visit[ma1.rx][ma1.ry][ma1.bx][ma1.by]= 1;

	int result = BFS();

	cout << result;

	system("pause");
	return 0;
}

int BFS()
{
	while (!Q.empty())
	{
		int rx = Q.front().rx;
		int ry = Q.front().ry;
		int bx = Q.front().bx;
		int by = Q.front().by;
		int cnt = Q.front().cnt;
		Q.pop();

		if (map[rx][ry] == 'O')
		{
			return cnt;
		}

		for (int i = 0; i < 4; i++)
		{

			int rnx = rx;
			int rny = ry;
			int bnx = bx;
			int bny = by;

			while ((map[rnx + dx[i]][rny + dy[i]] != '#' && map[rnx][rny] != 'O')) 
			{
				rnx += dx[i];
				rny += dy[i];
				//visit[rnx][rny].red = 1;
				
			}
			while ((map[bnx + dx[i]][bny + dy[i]] != '#' && map[bnx][bny] != 'O'))
			{
				bnx += dx[i];
				bny += dy[i];
				//visit[bnx][bny].blue = 1;
			}

			if (rnx == bnx && rny == bny)
			{
				if (map[rnx][rny] == 'O')continue;
				if ((abs(rnx - rx) + abs(rny - ry)) > (abs(bnx - bx) + abs(bny - by)))
				{
					//visit[rnx][rny].red = 0;
					rnx -= dx[i];
					rny -= dy[i];
					
				}
				else
				{
					//visit[bnx][bny].blue = 0;
					bnx -= dx[i];
					bny -= dy[i];
					
				}
			}

			if (visit[rnx][rny][bnx][bny]== 0)
			{
				Q.push({ rnx,rny,bnx,bny,cnt+1});
				visit[rnx][rny][bnx][bny] = 1;
			}

		}

	}
	return -1;
}

solarmagic 4년 전 0

red따로, blue따로 체크한다면 실제론 여태까지 방문한적 없었던 판의 구슬들의 배치인데 따로 따로 방문한 걸 보고 그 판을 이미 방문했다 생각하고 bfs가 진행되지 않겠네요.

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

문제

문제

출처

ICPC

2차원배열 2개와 4차원배열

wjavm2 4년 전 0

solarmagic 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말