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번만 돌려주면 된다.

#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,-1 };
int dy[] = { 1,-1,0,0 };
int chk(int x, int y) {
    return 0 <= x&&x < n && 0 <= y&&y < n;
}
int bfs(int state) {
    memset(disc, 0, sizeof(disc));
    queue<pair<int,int>> qu;
    bool c[10];
    for (int i = 0; i < 10; i++)
        c[i] = (1 << i)&state ? 1 : 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,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 - 1 && 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 ? -1 : r);
    }
    return 0;
}