글 읽기 - 도와주십시요.. 몇십번틀리느눙입니다..

zhh1020 5년 전 0

불을 BFS로 이동시키고 상근이를 이동시키는 방식으로 진행했습니다. 불이 없는경우와 있는 경우 다 나눠주었고, 맵을 벗어나는 경우를 고려하여 1002 1002 사이즈로 배열을 구성하였습니다..

#include <iostream>
#include <queue>
using namespace std;
struct Info {
	int y, x;
	int cnt;
};
queue<struct Info>Fire;
queue<struct Info>Sang;
const int MAX = 1003;

char map[MAX][MAX];
bool visit[MAX][MAX];
int T;
int w, h;
int dir[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };

bool In(int y, int x) {
	return y >= 1 && y <= h && x >= 1 && x <= w;
}

void BFS() {
	
	//불을 먼저 이동 시키고 상근이 이동
	struct Info temp;
	int cnt = 0;

	//불이 없을 경우
	if (Fire.size() == 0) {
		int CNT = 0;

		while (!Sang.empty()) {
			int SIZE = Sang.size();
			CNT++;
			for (int i = 0; i < SIZE; i++) {
				int current_y = Sang.front().y;
				int current_x = Sang.front().x;
				visit[current_y][current_x] = true;
				Sang.pop();
				for (int j = 0; j < 4; j++) {
					int dy = current_y + dir[j][0];
					int dx = current_x + dir[j][1];

					if (!In(dy, dx))
					{
						cout<<CNT << endl;
						return;
					}
					if (map[dy][dx] == '.' && visit[dy][dx] == false) {
						
						temp.x = dx;
						temp.y = dy;
						Sang.push(temp);
					}
				}

			}

		}
	}


	//불이 있을 경우
	while (!Fire.empty()) {
		/*for (int y = 1; y <= h; y++) {
			for (int x = 1; x <= w; x++) {
				visit[y][x] = false;
			}
		}*/

		int FIRE_SIZE = Fire.size();
		cnt++;
		for (int j = 0; j < FIRE_SIZE; j++) {
			int fire_y = Fire.front().y;
			int fire_x = Fire.front().x;
			visit[fire_y][fire_x] = true;
			Fire.pop();

			for (int i = 0; i < 4; i++) {
				int fire_dy = fire_y + dir[i][0];
				int fire_dx = fire_x + dir[i][1];
				if (In(fire_dy, fire_dx) && (map[fire_dy][fire_dx] == '.' || map[fire_dy][fire_dx] == '@') && visit[fire_dy][fire_dx] == false)	//상근이의 위치거나 , 빈공간이면 이동
				{
					//visit[fire_dy][fire_dx] = true;
					map[fire_dy][fire_dx] = '*';
					temp.y = fire_dy;
					temp.x = fire_dx;
					Fire.push(temp);
				}

			}
		}
		//현재 지난 시간만큼 불이 이동했다.
		//이제 상근이를 이동시킨다.

		
		int SANG_SISZE = Sang.size();
		for (int j = 0; j < SANG_SISZE; j++) {
			int sang_y = Sang.front().y;
			int sang_x = Sang.front().x;
			int sang_cnt = Sang.front().cnt;

			visit[sang_y][sang_x] = true;

			Sang.pop();
			for (int i = 0; i < 4; i++) {
				int sang_dy = sang_y + dir[i][0];
				int sang_dx = sang_x + dir[i][1];
				if (!In(sang_dy, sang_dx)) {	//상근이가 맵에서 벗어나면
					cout << cnt << endl;
					return;
				}
				if (map[sang_dy][sang_dx] == '.' && visit[sang_dy][sang_dx] == false) {
					temp.x = sang_dx;
					temp.y = sang_dy;
					temp.cnt = sang_cnt + 1;
					//cout << sang_dy << " " << sang_dx << endl;
					Sang.push(temp);
					//visit[sang_dy][sang_dx] = true;
				}

			}

		}
	}

	
	
	cout << "IMPOSSIBLE" << endl;
}
int main() {
	//cin.tie(NULL);
	//ios::sync_with_stdio(false);

	struct Info temp;

	cin >> T;

	for (int r = 0; r < T; r++) {
		//cout << endl<<endl;
		while (!Sang.empty())
			Sang.pop();
		while (!Fire.empty())
			Fire.pop();

		cin >> w >> h;

		for (int y = 1; y <= h; y++) {		//맵 입력
			for (int x = 1; x <= w; x++) {
				visit[y][x] = false;
				cin >> map[y][x];
				if (map[y][x] == '@') {
					temp.y = y;
					temp.x = x;
					temp.cnt = 0;
					Sang.push(temp);
				}
				else if (map[y][x] == '*') {
					temp.y = y;
					temp.x = x;
					Fire.push(temp);
				}
			}
		}

		BFS();




	}
}

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

문제

문제

출처

ICPC

도와주십시요.. 몇십번틀리느눙입니다..

zhh1020 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말