-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathbaekjoon16724.cpp
More file actions
65 lines (56 loc) ยท 1.25 KB
/
baekjoon16724.cpp
File metadata and controls
65 lines (56 loc) ยท 1.25 KB
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
#include<iostream>
using namespace std;
typedef pair<int, int> pii;
int N, M, answer;
string s;
char direction[1001][1001];
int record[1001][1001];
void DFS(int x, int y) { // ๋์ ๊ฒฝ์ฐ DFS๋ฅผ ํ๋, ๋ฐฉ๋ฌธ ๋ ๋ฒ ํ๋ฉด ์ข
๋ฃ์์ผ์ฃผ์๋ค.
if (record[x][y] == 1)
return;
if (record[x][y] == 0) {
answer++;
record[x][y] = 1;
return;
}
if (record[x][y] == -1) {
record[x][y] = 0;
}
int nx = x;
int ny = y;
if (direction[x][y] == 'D') {
nx += 1;
}
else if (direction[x][y] == 'U') {
nx -= 1;
}
else if (direction[x][y] == 'R') {
ny += 1;
}
else if (direction[x][y] == 'L') {
ny -= 1;
}
DFS(nx, ny);
record[x][y] = record[nx][ny];
}
//๊ธฐ๋ณธ ์์ด๋์ด : DFS๋ฅผ ํ๋ฉด์ ๊ฐ ์ ์๋ ๋ฐฉํฅ์ผ๋ก ๋ฐฉ๋ฌธ์ ํ๋, ์ฌ์ดํด์ด ์๊ธฐ๋ ๊ตฌ๊ฐ์ด save zone์ด๋ผ ์๊ฐ
//์ฌ์ดํด์ด ์๊ธด๋ค๋ ๊ฒ์ ๋ฐฉ๋ฌธํ๋ ๊ณณ์ ํ๋ฒ ๋ ๋ฐฉ๋ฌธํ๋ฉด ์ฌ์ดํด์ด๊ณ , ๊ทธ๋ฐ ์๊ฐ์ ์ ๋ต์ผ๋ก ๊ฐ์ฃผ
// ๊ทธ ๊ฒฝ์ฐ๊ฐ ์๋๋ผ, ๋ฐฉ๋ฌธ์ ํ๋๋ฐ ์ ์ด์ ์ฌ์ดํด์ด ์๊ฒผ๋ ์ฅ์์ด๋ฉด dfs๋ฅผ ํธ์ถํ ์์น ๋ํ ์ฌ์ดํด์ ํฌํจ๋๋ฏ๋ก ์ข
๋ฃ
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> M;
for (int i = 0; i < N; i++) {
cin >> s;
for (int j = 0; j < M; j++) {
record[i][j] = -1;
direction[i][j] = s[j];
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
DFS(i, j);
}
}
cout << answer;
}