글 읽기 - 도대체 어디가틀린건지모르겠어요ㅠㅠ고수님들!!

qudwn8418 4년 전 0

상근이의 최단경로와.. 불의 최단경로.. 구해서 비교하는걸로 접근했는데!

어디가 틀린건지모르겠어요 ㅠㅠ 혹시 반례나 틀린부분을 찾아주실 고수님들계신가요?

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

using namespace std;

char pmap[1001][1001];
int sang_map[1001][1001];
int fire_map[1001][1001];
int sang_visited[1001][1001];
int fire_visited[1001][1001];
queue<pair<int, int>> sang;
queue<pair<int, int>> fire;
queue<pair<int, int>> exit1;
queue < pair<int, int>> spotpoint;
queue<pair<int, int>> start;

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

int main(void) {

	int test;
	scanf("%d", &test);

	for (int t = 0; t < test; t++) {
		
		bool check = false;
		
		memset(sang_map, 0, sizeof(sang_map));



		memset(fire_map, 0, sizeof(sang_map));
		memset(sang_visited, 0, sizeof(sang_map));
		memset(fire_visited, 0, sizeof(sang_map));
		sang = start;
		fire = start;
		exit1 = start;
		spotpoint = start;

		int wid, hei;
		int min1 = 10000;
		int f_min = 10000;

		scanf("%d %d", &wid, &hei);

		for (int y = 0; y < hei; y++) {
			string input;
			cin >> input;
			for (int x = 0; x < wid; x++) {
				pmap[y][x] = input[x];
				if (input[x] == '@') {
					if (x == 0 || y == 0 || x == wid || y == hei) {
					
						check = true;
					}
					sang.push({ y,x });
				}
				else if (input[x] == '*') {
					fire.push({ y,x });
				}
				if (x == 0 || y == 0 || x == (wid - 1) || y == (hei - 1)) {
					if (input[x] == '.') {
						exit1.push({ y,x });
					}
				}
			}
		}

		if (check) {
			cout << "1" << endl;
			continue;
		}

		while (!sang.empty()) {				// 상근이의 경로에서 갈수있는곳까지 거리를 구함
			auto cur = sang.front(); sang.pop();
			//			if (sang_visited[cur.first][cur.second] == 1) continue;

			sang_visited[cur.first][cur.second] = 1;
			for (int dir = 0; dir < 4; dir++) {
				int nx = cur.second + dx[dir];
				int ny = cur.first + dy[dir];

				if (pmap[ny][nx] == '@' || pmap[ny][nx] == '#' || pmap[ny][nx] == '*') continue;
				if (nx < 0 || nx >= wid || ny < 0 || ny >= hei)continue;
				if (sang_visited[ny][nx] == 1) continue;

				sang.push({ ny,nx });
				sang_visited[ny][nx] = 1;
				sang_map[ny][nx] = sang_map[cur.first][cur.second] + 1;
			}


		}

		if (!exit1.empty()) {			// 탈출구가 존재 할 경우
			while (!exit1.empty()) {
				auto spot = exit1.front(); exit1.pop();
				if (min1 > sang_map[spot.first][spot.second] && sang_map[spot.first][spot.second] != 0) {
					min1 = sang_map[spot.first][spot.second];
					spotpoint.push({ spot.first,spot.second });
				}
			}

		}
		else {								//탈출구가 존재하지 않을경우
			cout << "IMPOSSIBLE" << endl;
			check = true;
			continue;
		}

		if (check) {
			continue;
		}

		if (min1 == 0) {					// 상근이가 탈출구로 이동할수있는 경로가 없을경우
			cout << "IMPOSSIBLE" << endl;
			check = true;
			continue;
		}

		if (check) {
			continue;
		}
		if (!fire.empty()) {				// 불이 있는 경우
		
			while (!fire.empty()) {
				int sz = fire.size();

				for (int f = 0; f < sz; f++) {
					auto cur = fire.front(); fire.pop();


					for (int dir = 0; dir < 4; dir++) {
						int nx = cur.second + dx[dir];
						int ny = cur.first + dy[dir];

						if (pmap[ny][nx] != '.') continue;
						if (nx < 0 || nx >= wid || ny < 0 || ny >= hei) continue;
						if (fire_visited[ny][nx] == 1) continue;

						fire.push({ ny,nx });
						fire_visited[ny][nx] = 1;
						fire_map[ny][nx] = fire_map[cur.first][cur.second] + 1;
					}

				}
			}

		}

		if (!spotpoint.empty()) {
			auto spot = spotpoint.back();
			f_min = fire_map[spot.first][spot.second];

			if (min1 <= f_min || f_min==0) {
				cout << min1 + 1 << endl;
				check = true;
				continue;
			}
			else {
				
				cout << "IMPOSSIBLE" << endl;
				check = true;
				continue;
			}
		}
		else {
			cout << "IMPOSSIBLE" << endl;
	
			check = true;
			continue;
		}

		if (check) {
			continue;
		}


	}

}

seico75 4년 전 2

7 6
###.###
#.*...#
#..@..#
#.....#
#.....#
###.###

답은 4인 것 같습니다.

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

문제

문제

출처

ICPC

도대체 어디가틀린건지모르겠어요ㅠㅠ고수님들!!

qudwn8418 4년 전 0

seico75 4년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말