https://www.acmicpc.net/problem/1577
(0, 0)에서 출발하여 (N, M)에 도착할 수 있는 경우의 수를 구하는문제입니다.
다만 이 문제는 공사중이어서 갈 수 없는 길이 존재하는데 거리는 항상 1이므로 set으로 관리하였습니다.
(a, b), (c, d) 형식으로 입력이 주어지면 (a, b)에서 (c, d)로 가는 길, (c, d)에서 (a, b)로 가는 길 모두 체크하였습니다.
로직은 dfs+dp으로 구성하였고, 이동은 최단거리로만 이동하기 때문에 뒤로는 가지 않아야합니다.
이 문제의 답은 long long 범위라고 명시되어 있으므로 long long으로 구해줍니다.
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
|
#include <iostream>
#include <set>
#include <cstring>
using namespace std;
typedef long long ll;
set<pair<int, int> > s[101][101];
ll dp[101][101];
int list[101][101];
int direct[2][2] = { {0,1},{1,0} };
int N, M, K;
ll func(int x, int y) {
if (x == N && y == M) return 1;
ll &ret = dp[x][y];
if (ret != -1) return ret;
ret = 0;
for (int i = 0; i < 2; i++) {
int nx = x + direct[i][0];
int ny = y + direct[i][1];
if (nx > N || ny > M) continue;
if (s[x][y].find({ nx,ny }) != s[x][y].end()) continue;
ret += func(nx, ny);
}
return ret;
}
void input() {
int sx, sy, ex, ey;
cin >> N >> M >> K;
while (K--) {
cin >> sx >> sy >> ex >> ey;
s[sx][sy].insert({ ex,ey });
s[ex][ey].insert({ sx,sy });
}
memset(dp, -1, sizeof(dp));
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
cout << func(0, 0) << '\n';
return 0;
}
|
cs |
'algorithm > dp' 카테고리의 다른 글
boj 14700 넴모넴모 (Hard) (0) | 2021.06.22 |
---|---|
boj 1311 할 일 정하기 1 (0) | 2021.06.21 |
boj 4781 사탕 가게 (0) | 2021.06.19 |
boj 2186 문자판 (0) | 2021.06.19 |
boj 13325 이진 트리 (0) | 2021.06.18 |