https://www.acmicpc.net/problem/1577
1577번: 도로의 개수
첫째 줄에 도로의 가로 크기 N과 세로 크기 M이 주어진다. N과 M은 100보다 작거나 같은 자연수이고, 둘째 줄에는 공사중인 도로의 개수 K가 주어진다. K는 0보다 크거나 같고, 100보다 작거나 같은
www.acmicpc.net
(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 |