範例程式碼 uva11624

//uva11624
#include <stdio.h>
#include <queue>

using namespace std;

char g[1010][1010];
int F[1010][1010], J[1010][1010];
int n, m, dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

struct pt {
    int x, y;
};
pt pf, pj;

queue<pt> Q;

void sol() {
	
    int i, j;
    while(!Q.empty()) Q.pop();
    pt tn, tx;
	
    for(i = 0; i < n; i++) {
        for(j = 0; j < m; j++) {
            if(g[i][j] == 'F') {
                pf.x = i, pf.y = j;
                Q.push(pf);
                F[pf.x][pf.y] = 1;
            }		
		}
	}

    while(!Q.empty()) {
        tn = Q.front();
        Q.pop();
        for(i = 0; i < 4; i++) {
            tx.x = tn.x + dir[i][0];
            tx.y = tn.y + dir[i][1];
            if(tx.x < 0 || tx.x >= n || tx.y < 0 || tx.y >= m)
                continue;
            if(g[tx.x][tx.y] == '#')
                continue;
            if(F[tx.x][tx.y] == 0) {
                F[tx.x][tx.y] = F[tn.x][tn.y] + 1;
                Q.push(tx);
            }
        }
    }
    Q.push(pj), J[pj.x][pj.y] = 1;
    while(!Q.empty()) {
        tn = Q.front();
        Q.pop();
        if(tn.x == 0 || tn.y == 0 || tn.x == n-1 || tn.y == m-1) {
            printf("%d\n", J[tn.x][tn.y]);
            return;
        }
        for(i = 0; i < 4; i++) {
            tx.x = tn.x + dir[i][0];
            tx.y = tn.y + dir[i][1];
            if(tx.x < 0 || tx.x >= n || tx.y < 0 || tx.y >= m)
                continue;
            if(g[tx.x][tx.y] == '#')
                continue;
            if(J[tx.x][tx.y] == 0 && (J[tn.x][tn.y] + 1 < F[tx.x][tx.y] || F[tx.x][tx.y] == 0)) {
                J[tx.x][tx.y] = J[tn.x][tn.y] + 1;
                Q.push(tx);
            }
        }
    }
    puts("IMPOSSIBLE");
}
int main() {
    int t, i, j;
    scanf("%d", &t);
    while(t--) {
        scanf("%d %d", &n, &m);
        for(i = 0; i < n; i++) {
            scanf("%s", g[i]);
            for(j = 0; j < m; j++) {
                if(g[i][j] == 'J')
                    pj.x = i, pj.y = j;
                F[i][j] = 0, J[i][j] = 0;
            }
        }
        sol();
    }
    return 0;
}