쉬운 최단거리

https://www.acmicpc.net/problem/14940

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	10064	4069	3279	38.084%

문제

지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.

문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.

입력

지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000)

다음 n개의 줄에 m개의 숫자가 주어진다.

0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다.

출력

각 지점에서 목표지점까지의 거리를 출력한다. 

원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다.

예제 입력 1

15 15
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 0 0 0
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1

예제 출력 1

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
11 12 13 14 15 16 17 18 19 20 0 0 0 0 25
12 13 14 15 16 17 18 19 20 21 0 29 28 27 26
13 14 15 16 17 18 19 20 21 22 0 30 0 0 0
14 15 16 17 18 19 20 21 22 23 0 31 32 33 34

출처

University > 서강대학교 > 2017 Sogang Programming Contest > Master F번

• 문제를 만든 사람: semteo04

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

---

통과된 코드

#include <iostream>
#include <queue>
using namespace std;
int _N, _M, _Map[1000][1000], _Temp;
bool _IsVisted[1000][1000];
int _DxDy[4][2] = {{ 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 }};
pair<int, int> _CntPos, _StartPos;
queue<pair<int, pair<int, int>>> _BfsQueue;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> _N >> _M;
	for (int i = 0; i < _N; i++)
		for (int j = 0; j < _M; j++) {
			cin >> _Temp;
			_Map[i][j] = _Temp;
			if (_Temp == 2)_StartPos = make_pair(i, j);
			else if (_Temp == 0) _IsVisted[i][j] = true;	
		}

	_BfsQueue.push(make_pair(0, _StartPos));
	_IsVisted[_StartPos.first][_StartPos.second];
	while (!_BfsQueue.empty()) {
		_CntPos = _BfsQueue.front().second;
		int _cnt = _BfsQueue.front().first;
		_BfsQueue.pop();
		for (int i = 0; i < 4; i++) {
			int _dx = _CntPos.first + _DxDy[i][0];
			int _dy = _CntPos.second + _DxDy[i][1];

			if (_dx >= _N || _dy >= _M || _dx < 0 || _dy < 0 || _IsVisted[_dx][_dy])
				continue;
			_IsVisted[_dx][_dy] = true;
			_Map[_dx][_dy] = _cnt + 1;
			_BfsQueue.push(make_pair(_cnt + 1, make_pair(_dx, _dy)));
		}
	} 
	_Map[_StartPos.first][_StartPos.second] = 0;
	for (int i = 0; i < _N; i++) {
		for (int j = 0; j < _M; j++) {
			if (!_IsVisted[i][j]) cout << -1 << " ";
			else cout << _Map[i][j] << " ";	
		}
		cout << "\n";
	}

	return 0;
}

원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1 부분을 처리 안해줘서 실패.