글 읽기 - 이상하게 bfs로 짤때마다 69프로에서 틀리네요.ㅠㅠ

baek_su 5년 전 1

예전에도 69프로에서 틀려서 2주정도 있다가 다시 bfs로 짜봤는데...

계속 틀리네요....

어떤걸 놓치고 있을까요..ㅠㅠㅠㅠㅠ

#include <iostream>
#include <queue>
using namespace std;

class Ball
{
public:
	int rx;
	int ry;
	int bx;
	int by;

	int time;
	int dir;
	Ball() {
		time = 0;
		dir = -1;
	}
	Ball(int ary , int arx ,  int aby , int abx , int atime, int adir)
	{
		rx = arx;
		ry = ary;
		bx = abx;
		by = aby;
		time = atime;
		dir = adir;
	}


};


int N, M;

char map[11][11];
int dy[4] = {-1,0,0,1 };
int dx[4] = { 0,-1,1,0 };

Ball ball;

bool blue_out = false;
bool red_out = false;

int ans = -1;

void move(int &ry, int &rx, int &by, int &bx, int dir);
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] == 'B')
			{
				ball.by = i;
				ball.bx = j;
				
			}
			else if (map[i][j] == 'R')
			{	
				ball.ry = i;
				ball.rx = j;
			
			}
		}
	}
	
	ans = BFS();
	

	cout << ans << '\n';



	return 0;
}


int BFS()
{
	queue<Ball> q;

	q.push(ball);

	while (!q.empty())
	{
	
		int cur_ry = q.front().ry;
		int cur_rx = q.front().rx;
		int cur_by = q.front().by;
		int cur_bx = q.front().bx;
		int cur_time = q.front().time;
		int cur_dir = q.front().dir;
		q.pop();

		//10번을 넘어가면 그냥 종료
		if (cur_time > 10)
			return -1;


		//4방향으로 bfs를 할거다 
		for (int i = 0; i < 4; i++)
		{
			blue_out = false;
			red_out = false;

			//맨처음을 제외하고는 이전에 왔던 방향이나 이전방향의 반대방향으로 가려고하는거는 제외시킨다.
			if (cur_dir != -1)
			{
				if (cur_dir == i || cur_dir + i == 3)
					continue;
			}

			//이동이 일어난후 좌표들 
			int temp1 = cur_ry;
			int temp2 = cur_rx;
			int temp3 = cur_by;
			int temp4 = cur_bx;

			//이동실시
			move(temp1, temp2, temp3 , temp4 , i);

			//움직여봤는데 파란공이 아웃되면 큐에 넣어주지 않고 다음방향 체크 
			if (blue_out)
				continue;

			if (red_out)
				return cur_time + 1;


			q.push(Ball(temp1, temp2, temp3, temp4, cur_time + 1,i));

		}
	}
}


void move(int &ry, int &rx , int &by, int &bx , int dir)
{
	//파란공 위치 
	int n_by = by;
	int n_bx = bx;
	int b_dist = 0;

	while (1)
	{

		
		//파란공이 나가버리면 그냥 종료 
		if (map[n_by + dy[dir]][n_bx + dx[dir]] == 'O')
		{
			blue_out = true;
			return;
		}

		//벽이면 이동 끝
		if (map[n_by + dy[dir]][n_bx + dx[dir]] == '#')
			break;
		

		n_by = n_by + dy[dir];
		n_bx = n_bx + dx[dir];
		b_dist++;
	}


	//다음 빨간공의 위치
	int n_ry = ry;
	int n_rx = rx;
	int r_dist = 0;

	while (1)
	{
	
		//빨간공이 탈출성공하면 true로 바꿔주고 return해준다.
		if (map[n_ry + dy[dir]][n_rx + dx[dir]] == 'O')
		{
			red_out = true;
			return;
		}

		if (map[n_ry + dy[dir]][n_rx + dx[dir]] == '#')
			break;

		n_ry = n_ry + dy[dir];
		n_rx = n_rx + dx[dir];
		r_dist++;
	}

	//같은위치라면 움직인 칸의 개수를 이용하여 위치를 조정해준다.
	if (n_ry == n_by && n_rx == n_bx)
	{
		if (b_dist > r_dist)
		{
			n_by = n_by - dy[dir];
			n_bx = n_bx - dx[dir];
		}
		else
		{
			n_ry = n_ry - dy[dir];
			n_rx = n_rx - dx[dir];
		}
	}

	//공들 위치 갱신 
	ry = n_ry;
	rx = n_rx;
	by = n_by;
	bx = n_bx;


}