본문 바로가기

알고리즘 관련/UVaOJ

UVaOJ)12797 Letters

문제:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4662


NxN의 맵이 주어질 때 1,1에서 n,n까지의 최단거리를 구하는 문제이다.


단 제약조건이 있는데 발판으로 주어지는 알파벳중에 대문자나 소문자 하나를 정해놓고 일관성있게 밟아야 한다.


알파벳이 최대 10개밖에 없기 때문에 상태에 대하여 비트마스킹을하여 넘겨주어 BFS를 1024번만 돌려주면 된다.


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
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#define INF 987654321
using namespace std;
int n, disc[101][101];
char a[101][101];
int dx[] = { 0,0,1,-};
int dy[] = { 1,-1,0,};
int chk(int x, int y) {
    return <= x&&< n && <= y&&< n;
}
int bfs(int state) {
    memset(disc, 0sizeof(disc));
    queue<pair<int,int>> qu;
    bool c[10];
    for (int i = 0; i < 10; i++)
        c[i] = (<< i)&state ? 0;
    if ('A' <= a[0][0&& a[0][0<= 'Z'&&!c[a[0][0- 'A'])
        return INF;
    if ('a' <= a[0][0&& a[0][0<= 'z'&&c[a[0][0- 'a'])
        return INF;
    qu.push({ 0,});
    disc[0][0= 1;
    int ret = 1;
    while (qu.size()) {
        int qs = qu.size();
        while (qs--) {
            int x = qu.front().first;
            int y = qu.front().second;
            qu.pop();
            if (x == n - && y == n - 1)
                return ret;
            for (int i = 0; i < 4; i++) {
                int cx = x + dx[i];
                int cy = y + dy[i];
                if (disc[cx][cy] || !chk(cx, cy))continue;
                if ('a' <= a[cx][cy] && a[cx][cy] <= 'z'&&c[a[cx][cy] - 'a'])
                    continue;
                if ('A' <= a[cx][cy] && a[cx][cy] <= 'Z'&&!c[a[cx][cy] - 'A'])
                    continue;
                disc[cx][cy] = 1;
                qu.push({ cx,cy });
            }
        }
        ret++;
    }
    return INF;
}
int main(){
    while (scanf("%d"&n) != EOF) {
        for (int i = 0; i < n; i++)
            scanf("%s"&a[i]);
        int r = INF;
        for (int i = 0; i < 1024; i++
            r = min(r, bfs(i));
        printf("%d\n", r == INF ? -: r);
    }
    return 0;
}
cs


'알고리즘 관련 > UVaOJ' 카테고리의 다른 글

UVaOJ)12797 Letters  (0) 2017.06.27
UVaOJ)11765 Component Placement  (0) 2017.06.27
UVaOJ)12159 Gun Fight  (0) 2017.06.27
UVaOJ)12878 Flowery Trails  (0) 2017.06.23
UVaOJ)10968 KuPellaKeS  (0) 2017.06.20
UVaOJ)12645 Water Supply  (0) 2017.06.19

태그