#include<iostream>
#include<queue>
using namespace std;

struct M
{
    int i,j,step;  // i是行  j是列  step记录步数
}map;
char A[305][305],B[305][305]; 
int bfs(int endm,int endn);
int main()
{
    int n,m,i,j,endm,endn;
    while(cin>>m>>n)
    {
        if(m==0 && n==0)
             break;
        for(i=1;i<=m;i++)
            for(j=1;j<=n;j++)
            {
                cin>>A[i][j];
                if(A[i][j] == 'Y')
                {
                    map.i = i; map.j = j; map.step = 0; //记下初始位置
                }
                if(A[i][j] == 'T')
                {
                    endm = i; endn = j;    //记下目标位置
                }
            }
        for(i=0;i<=m+1;i++)   //下面的两个并列for循环是将A数组的外面一周围上S
        {
            A[i][0] = 'S';
            A[i][n+1] = 'S';
        }
        for(i=0;i<=n+1;i++)
        {
            A[0][i] = 'S';
            A[m+1][i] = 'S';
        }
        for(i=1;i<=m;i++)          //将A数组复制一份存在B中
            for(j=1;j<=n;j++)
                B[i][j] = A[i][j];
            
        j=bfs(endm,endn);   
        if(j>=0)
        cout<<j<<endl;
        else cout<<"-1"<<endl;
    }
    return 0;
}

int bfs(int endm,int endn)
{
    queue<M> Q;
    M cur,tt,t;
    int i,dist1[4] = {0,0,-1,1};
    int dist2[4] = {-1,1,0,0};
    Q.push(map);
    while(!Q.empty())
    { 
        cur = Q.front();
        Q.pop();
        for(i=0;i<4;i++)     //向四个方向搜索
        {
            tt.i = cur.i + dist1[i];
            tt.j = cur.j + dist2[i];
            if(A[tt.i][tt.j] == 'E' || (tt.i == endm && tt.j == endn))
            {
                tt.step = cur.step +1;
                if(B[tt.i][tt.j] == 'B') //说明这个E是我用B换来的,所以要再加一步
                     tt.step = tt.step + 1;   
                Q.push(tt);
                A[tt.i][tt.j] = 'S';  //不允许以后再访问了 
            }
            else if(A[tt.i][tt.j] == 'B')//如果遇到B,让当前出队的元素保留原来的 
step再次入队,并把B换成E,以便能再次访问.
            {
                tt.step = cur.step;
                tt.i = cur.i;
                tt.j = cur.j;
                Q.push(tt);
                A[tt.i+dist1[i]][tt.j+dist2[i]] = 'E';
            }     
            if(tt.i == endm && tt.j == endn) //一旦遇到目的地就一定是最短的.
                return tt.step;           
        }
    }
    return -1;
}

• Re:高手帮忙看看我的代码,错在哪里了,总是WA,我有详细的注释,很易看懂,谢谢 ! (8) bingsanchun 2014-02-21 09:33:30