달리기

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	512 MB	6166	897	587	13.454%

문제

진영이는 다이어트를 위해 N×M 크기의 체육관을 달리려고 한다.

체육관은 1×1 크기의 칸으로 나누어져 있고, 칸은 빈 칸 또는 벽이다. 

x행 y열에 있는 칸은 (x, y)로 나타낸다.

매 초마다 진영이는 위, 아래, 오른쪽, 왼쪽 중에서 이동할 방향을 하나 고르고,

그 방향으로 최소 1개, 최대 K개의 빈 칸을 이동한다.

시작점 (x₁, y₁)과 도착점 (x₂, y₂)가 주어졌을 때,

시작점에서 도착점으로 이동하는 최소 시간을 구해보자.

입력

첫째 줄에 체육관의 크기 N과 M, 1초에 이동할 수 있는 칸의 최대 개수 K가 주어진다.

둘째 줄부터 N개의 줄에는 체육관의 상태가 주어진다.

체육관의 각 칸은 빈 칸 또는 벽이고, 빈 칸은 ‘.’, 벽은 ‘#’으로 주어진다.

마지막 줄에는 네 정수 x₁, y₁, x₂, y₂가 주어진다.

두 칸은 서로 다른 칸이고, 항상 빈 칸이다.

출력

(x₁, y₁)에서 (x₂, y₂)로 이동하는 최소 시간을 출력한다.

이동할 수 없는 경우에는 -1을 출력한다.

제한

• 2 ≤ N, M ≤ 1,000
• 1 ≤ K ≤ 1,000
• 1 ≤ x₁, x₂ ≤ N
• 1 ≤ y₁, y₂ ≤ M

예제 입력 1

3 4 4
....
###.
....
1 1 3 1

예제 출력 1

3

예제 입력 2

3 4 1
....
###.
....
1 1 3 1

예제 출력 2

8

예제 입력 3

2 2 1
.#
#.
1 1 2 2

예제 출력 3

-1

출처

• 문제를 번역한 사람: baekjoon
• 데이터를 추가한 사람: djm03178
• 문제의 오타를 찾은 사람: doju, psi0613, seico75
• 빠진 조건을 찾은 사람: jh05013

알고리즘 분류

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

---

추가 반례

예제 입력 A

2 2 1
..
..

0 0 0 0

예제 출력 A

0

예제 입력 B

7 4 4
....
.##.
..#.
#.#.
#...
#.##
#.##
1 1 7 2

예제 출력 B

3

예제 입력 C

7 4 4
....
.##.
.#..
.#.#
...#
##.#
##.#
1 4 7 3

예제 출력 C

3

visited 배열에 방문하는 시점을 넣고 해결하는 경우

if (_isVisted[_dx][_dy] == _cnt)
break;

위 로직으로 진행한다면 탐색하는 방향의 순서(상, 하, 좌, 우)에 따라 답이 3 ~ 4로 달라집니다.

예제 입력 D

3 3 3
..#
..#
#..
1 1 3 3

예제 출력 D

3

통과된 코드

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

int _N, _M, _K, _Temp1, _Temp2, _Res;
int _DxDy[4][2] = { { 1, 0}, { -1, 0}, { 0, 1}, { 0, -1} };
char _Map[1000][1000];
int _isVisted[1000][1000];
string _Str;
pair<int, int> _sePos[2];
queue<pair<int, pair<int, int>>> _BFSQueue;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> _N >> _M >> _K;
	for (int i = 0; i < _N; i++) {
		cin >> _Str;
		for (int j = 0; j < _M; j++) 
			_Map[i][j] = _Str[j];
	}
	for (int i = 0; i < 2; i++) {
		cin >> _Temp1 >> _Temp2;
		_sePos[i] = make_pair(_Temp1 - 1, _Temp2 - 1);
	}

	for (int i = 0; i < _N; i++) 
		for (int j = 0; j < _M; j++)
			_isVisted[i][j] = INT32_MAX;
	
	_BFSQueue.push(make_pair(0, _sePos[0]));
	_isVisted[_sePos[0].first][_sePos[0].second] = 0;
	pair<int, int> _CntPos;
	int _dx, _dy, _cnt;
	while (!_BFSQueue.empty()) {
		_CntPos = _BFSQueue.front().second;
		_cnt = _BFSQueue.front().first;
		_BFSQueue.pop();
		if (_CntPos == _sePos[1]) {
			_Res = _cnt;
			break;
		}
		_cnt++;
		for (int i = 0; i < 4; i++) {
			for (int j = 1; j <= _K; j++) {
				_dx = _CntPos.first + _DxDy[i][0] * j;
				_dy = _CntPos.second + _DxDy[i][1] * j;
				if (_dx >= _N || _dy >= _M || _dx < 0 || _dy < 0 || _Map[_dx][_dy] == '#')
					break;
				if (_isVisted[_dx][_dy] < _cnt)
					break;
				if (_isVisted[_dx][_dy] == _cnt)
					continue;

				_BFSQueue.push(make_pair(_cnt, make_pair(_dx,_dy)));
				_isVisted[_dx][_dy] = _cnt;
			}
		}
	}

	if (_sePos[0] == _sePos[1]) cout << _Res;
	else if (_Res == 0) cout << -1;
	else cout << _Res;

	return 0;
}