티스토리 뷰

알고리즘 관련/UVaOJ

UVaOJ)12797 Letters

JASON 자손9319 2017. 6. 27. 15:48

문제: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
TAG
댓글
댓글쓰기 폼