题目：http://poj.org/problem?id=3984

解法1：（推荐）

#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio> 

using namespace std;

const int N = 10;
typedef pair<int,int>PII;

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
PII suc[N][N];
char g[N][N];

void bfs(){
    queue<PII>q;
    q.push({4, 4});
    g[4][4] = '1';
    while(q.size()){
        PII u = q.front();
        q.pop();
        for(int i = 0; i < 4; i ++ ){
            int a = u.first + dx[i], b = u.second + dy[i];
            if(a >= 0 && b >= 0 && a < 5 && b < 5 && g[a][b] == '0'){
                g[a][b] = '1';
                q.push({a, b});
                suc[a][b] = u;
                if(!a && !b)    return ;
            }
        }
    }
}

int main(){
    for(int i = 0; i < 5; i ++ )
        for(int j = 0; j < 5; j ++ )
            cin>>g[i][j];
    bfs();
    int x = 0, y = 0;
    while(true){
        printf("(%d, %d)\n", x, y);
        int a = suc[x][y].first, b = suc[x][y].second;
        x = a, y = b;
        if(x == 4 && y == 4)    break;
    }
    printf("(4, 4)");
    return 0;
}

解法2：（适用500左右的二维数组，否则要tle）

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cstdio>

using namespace std;

typedef pair<int,int>PII;
const int N = 505;

int g[N][N];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
char pos1[4] = {'d', 'l', 'u', 'r'};
int pos2[26];
bool  st[N][N];

void bfs(){
    queue<PII>q;
    queue<string>path;
    q.push({0, 0});
    path.push("u");
    pos2['d' - 'a'] = 0;pos2['l' - 'a'] = 1;pos2['u' - 'a'] = 2;pos2['r' - 'a'] = 3;
    while(q.size()){
        PII u = q.front();q.pop();
        string s = path.front();path.pop();
        for(int i = 0; i < 4; i ++ ){
            int a = dx[i] + u.first, b = dy[i] + u.second;
            if(g[a][b] == 0 && a >= 0 && b >= 0 && a < 5 && b < 5 && !st[a][b]){
                st[a][b] = true;
                q.push({a, b});
                path.push(s + pos1[i]);
                if(a == 4 && b == 4){
                    while(q.size()) q.pop();
                    while(path.size() > 1)  path.pop();
                    break;
                }
            }
        }
    }
    string s = path.front();
    int x = 0, y = 0;
    printf("(0, 0)\n");
    for(int i = 1; i < s.size(); i ++ ){
        int c = s[i] - 'a';
        x = dx[pos2[c]] + x, y = dy[pos2[c]] + y;
        printf("(%d, %d)\n", x, y);
    }
}

int main(){
    for(int i = 0; i < 5; i ++ )
        for(int j = 0; j < 5; j ++ )
            cin>>g[i][j];
    bfs();  
    return 0;
}