範例程式碼 uva12797

//uva12797
/// brute-force + bfs
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <iostream>
#define INF (1<<30)

using namespace std;

char m[105][105];
bool vis[105][105];
bool p[256]; /// permission
int N, ans;
int dir[4][2] = {{0,1}, {1,0}, {0,-1}, {-1,0}};

class Pos{
public:
    int x, y, c;
    Pos() {}
    Pos(int _x, int _y, int _c = 1): x(_x), y(_y), c(_c) {}
    bool legal() { return (x >= 1 && x <= N && y >= 1 && y <= N && p[m[x][y]] == true && vis[x][y] == false); }
};

bool finish(Pos cur) {
    return (cur.x == N && cur.y == N);
}

void bfs() {
    if (p[m[1][1]] == false || p[m[N][N]] == false) /// no permission in begin or end.
        return;

    queue<Pos> myq;
    while(!myq.empty()) 
		myq.pop();
    Pos cur, nxt, goal;
    memset(vis, false, sizeof(vis));
    myq.push(Pos(1, 1, 1));
    vis[1][1] = true;

    while(!myq.empty()) {
        cur = myq.front(); 
        myq.pop();
        if (finish(cur) == true) {
            ans = min(ans, cur.c);
            return;
        }
        for (int i = 0; i < 4; i++){
            nxt = Pos(cur.x + dir[i][0], cur.y + dir[i][1], cur.c + 1);
            if (nxt.legal() == true) {
                vis[nxt.x][nxt.y] = true;
                myq.push(nxt);
            }
        }
    }
}

void rec(int i) {
    if (i == 10)
        bfs();
    else {
        p[i + 'a'] = true;
        rec(i + 1);
        p[i + 'a'] = false;
        p[i + 'A'] = true;
        rec(i + 1);
        p[i + 'A'] = false;
    }
}

void solve() {
    memset(p,false,sizeof(p));
    rec(0); /// recursive to trace all permutation for 0~9 (a~j)
}

int main() {
    while(scanf("%d", &N) == 1) {
        for (int i = 1; i <= N; i++)
            scanf("%s", m[i] + 1);
        ans = INF;
        solve();
        printf("%d\n",ans == INF ? -1 : ans);
    }
    return 0;
}