coding_test/14923.cpp at boj · bae-jae/coding_test · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <iostream>
#include <queue>

using namespace std;

int map[1005][1005];
int visited[1005][1005][2];
int startX, startY;
int exitX, exitY;
int endX, endY;

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

int outRange(int x, int y)
{
	if(x < 1 || x >= (endX + 1))
		return 0;

	if(y < 1 || y >= (endY + 1))
		return 0;

	return 1;
}
int main(void)
{
	cin >> endX >> endY;
	cin >> startX >> startY;
	cin >> exitX >> exitY;

	for(int i = 1; i <= endX; ++i)
	{
		for(int j = 1; j <= endY; ++j)
		{
			int s;
			cin >> s;

			map[i][j] = s;
		}
	}


	//			    행	열      벽부슨 움직인 횟수
	queue<pair<pair<int, int>, pair<int, int>>> q;
	q.push({{startX, startY}, {1, 0}});

	while(!q.empty())
	{
		int mx = q.front().first.first;
		int my = q.front().first.second;

		int broke = q.front().second.first;
		int cost = q.front().second.second;

		q.pop();

		if(visited[mx][my][broke] == 1)
			continue;

		visited[mx][my][broke] = 1;

		if(mx == exitX && my == exitY)
		{
			cout << cost;
			return 0;
		}

		for(int i = 0; i < 4; ++i)
		{
			int rx = mx + dy[i];
			int ry = my + dx[i];

			if(outRange(rx, ry) == 1)
			{
				if(visited[rx][ry][broke] == 1)
					continue;

				if(map[rx][ry] == 1)
				{
					if(broke == 1)
					{
						q.push({{rx, ry}, {0, cost + 1}});
					}
					else
						continue;
				}
				else{
					q.push({{rx, ry}, {broke, cost + 1}});
				}

			}
		}
	}
	cout << -1;
}