글 읽기 - 틀렸다고 뜹니다

rlarlejr282 5년 전 0

주어진 맵에서 불이 얼마나 빨리 번지는지 기록하는 2차배열이랑

상근이가 얼마나 빨리 도망치는지 기록하는 2차배열을 사용했습니다

상근이가 다음 장소를 고려할 때

현재 장소에서 방문하는게 이득이고 불이 다음 장소에 도착하는 것 보다 빠르게 갈 수 있으면

다음 칸을 방문하도록 짰습니다.

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

int n, m;
char map[1001][1001];
int dx[] = { -1,0,1,0 };
int dy[] = { 0,-1,0,1 };
int fire[1001][1001];
int person[1001][1001];
queue <pair<int, int>> f;
queue <pair<int, int>> p;
bool inside(int x, int y) {
	if (x < 0 || y < 0 || x >= n || y >= m) return false;
	return true;
}
void show() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << map[i][j] << " ";
		}
		cout << "\n";
	}
	cout << "\n";
}
void showFire() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if(fire[i][j] == 1e9 || fire[i][j] == -1){
				cout << "F ";
			}
			else
				cout << fire[i][j] << " ";
		}
		cout << "\n";
	}
	cout << "\n";
}
void showPerson() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (person[i][j] == 1e9 || person[i][j] == -1) {
				cout << "F ";
			}
			else
				cout << person[i][j] << " ";
		}
		cout << "\n";
	}
	cout << "\n";
}
void clear() {
	for (int i = 0; i < 1001; i++) {
		for (int j = 0; j < 1001; j++) {
			fire[i][j] = 1e9;
			person[i][j] = 1e9;
		}
	}
}
int main() {
	//freopen("test.txt", "r", stdin);
	int testCase; cin >> testCase;
	while (testCase--) {
		clear();
		cin >> m >> n;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				cin >> map[i][j];
				if (map[i][j] == '*') {
					fire[i][j] = 0;
					f.push({ i,j });
					person[i][j] = 1e9;
				}
				if (map[i][j] == '@') {
					person[i][j] = 0;
					p.push({ i,j });
					fire[i][j] = 1e9;
				}
				if (map[i][j] == '#') {
					fire[i][j] = -1;
					person[i][j] = -1;
				}
				if (map[i][j] == '.') {
					fire[i][j] = 1e9;
					person[i][j] = 1e9;
				}
			}
		}

		while (!f.empty()) {
			int cx = f.front().first;
			int cy = f.front().second;
			f.pop();
			for (int i = 0; i < 4; i++) {
				int nx = cx + dx[i];
				int ny = cy + dy[i];
				if (!inside(nx, ny))continue;
				if (map[nx][ny] == '#') continue;
				if (fire[nx][ny] > fire[cx][cy] + 1) {
					fire[nx][ny] = fire[cx][cy] + 1;
					f.push({ nx,ny });
				}
			}
		}
		while (!p.empty()) {
			int cx = p.front().first;
			int cy = p.front().second;
			p.pop();
			for (int i = 0; i < 4; i++) {
				int nx = cx + dx[i];
				int ny = cy + dy[i];
				if (!inside(nx, ny))continue;
				if (map[nx][ny] == '#' || map[nx][ny] == '*')continue;
				if (person[nx][ny] > person[cx][cy] + 1 && 
					person[cx][cy] + 1 < fire[nx][ny]) {
					person[nx][ny] = person[cx][cy] + 1;
					p.push({ nx,ny });
				}
			}
		}
		int answer = 0;
		for (int i = 0; i < n; i++) {
			if (i == 0) {
				for (int j = 0; j < m; j++) {
					if (person[i][j] == 1e9 || person[i][j] == -1)continue;
					if(answer < person[i][j])
						answer =person[i][j];
				}
			}
			if (0 < i && i < n - 1) {
				for (int j = 0; j < m; j++) {
					if (0 < j && j < m - 1)continue;
					if (person[i][j] == 1e9 || person[i][j] == -1)continue;
					if(answer < person[i][j])
						answer =person[i][j];
				}
			}
			if (i == n - 1) {
				for (int j = 0; j < m; j++) {
					if (person[i][j] == 1e9 || person[i][j] == -1)continue;
					if (answer < person[i][j])
						answer = person[i][j];
				}
			}
		}
		//show();
		//showFire();
		//showPerson();
		if (answer == 0)
			cout << "IMPOSSIBLE\n";
		else
			cout << answer + 1 << "\n";
	}
}

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

문제

문제

출처

ICPC

틀렸다고 뜹니다

rlarlejr282 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말