16928 뱀과 사다리 게임

www.acmicpc.net/problem/16928

16928번: 뱀과 사다리 게임

 

전형적인 BFS 문제.

1번칸부터 100칸까지 있으며 10 X 10 맵으로 되어있다. 하지만 이 문제에서는 그냥 100칸짜리 1차원 배열에 넣어도 상관 없다.

1번칸에서 100번칸까지 가면 되는 문제.

주사위를 굴려 1칸부터 6칸까지 갈 수 있으며, 해당 칸에 사다리가 있으면 더 앞으로(+), 뱀이 있으면 뒤로(-) 움직이게 된다.

 

100칸 int 배열에 사다리, 뱀 유무 정보(0 이상)와 점프할 칸 정보를 저장한다.

(0 이면 사다리, 뱀 없음, 0이 아니면 점프할 칸)

 

한번 방문했던 곳은 다시 방문할 필요없다. 다시 방문해도 이전 방문보다 더 빨리 100번째 칸에 도착할 수 없다.

 

1번칸을 Queue에 넣고 BFS를 돌리면 된다.

 

 

 

#include <bits/stdc++.h>
using namespace std;
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
typedef long long lld;
 
int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, m;
    cin >> n >> m;
    vector<int> mp(101, 0), port(101, 0);
    vector<bool> check(101, false);
    n += m;
    for(int i=1;i<101;i++) mp[i] = i;
    for(int i=0;i<n;i++)
    {
        int x, y;
        cin >> x >> y;
        port[x] = y;
    }
    queue<int> q;
    q.push(1);
    check[1] = true;
    int cnt = 0;
    bool flag = false;
    while(!q.empty())
    {
        int size = q.size();
        while(size--)
        {
            int pos = q.front();
            q.pop();
            if(pos == 100)
            {
                cout << cnt;
                return 0;
            }
            for(int i=1;i<7;i++)
            {
                int tmp = pos+i;
                if(check[tmp] || tmp>100) continue;
                if(port[tmp])      q.push(port[tmp]);
                else q.push(tmp);
                check[tmp] = check[port[tmp]] = true;
            }
        }
        cnt++;
    }
 
    return 0;
}