그래프/BFS

스타트링크

4gats 2023. 5. 26. 14:44

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

 

5014번: 스타트링크

첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다.

www.acmicpc.net

숨바꼭질과 '똑같은' 문제이다

 

다만!!! 

bool check[1000001];
int dist[1000001];

범위보다 크게 설정하는 것을 까먹지말자!!! 제발!!!!

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
#include <iostream>
#include <queue>
 
using namespace std;
 
bool check[1000001];
int dist[1000001];
 
int main()
{
    int f, s, g, u, d;
 
    cin >> f >> s >> g >> u >> d;
 
    
    check[s] = true;
    dist[s] = 0;
    queue<int> q;
    q.push(s);
 
 
    while (!q.empty())
    {
        int now = q.front();
        q.pop();
        if (now - d >= 1)
        {
            if (check[now - d] == false)
            {
                q.push(now - d);
                check[now - d] = true;
                dist[now - d] = dist[now] + 1;
            }
        }
 
        if (now + u <= f)
        {
            if (check[now + u] == false)
            {
                q.push(now + u);
                check[now + u] = true;
                dist[now + u] = dist[now] + 1;
            }
        }
 
    }
 
    if (dist[g] != 0)
        cout << dist[g] << '\n';
    else
    {
        if (s == g)
            cout << 0 << '\n';
        else
            cout << "use the stairs" << '\n';
    }
 
    return 0;
}
 cs