記憶化廣度優先搜索，或者動態規劃。

狀態設定

* F[i,j,k] 表示從源點走到點(i,j)移動方向爲k時，轉彎的最小次數 

狀態轉移方程

* F[i,j,k]= min
      o {
            + F[i+1,j,l] + m
            + F[i-1,j,l] + m
            + F[i,j+1,l] + m
            + F[i,j-1,l] + m 
      o } 

產生新狀態時，如果方向改變，m爲1，否則m爲0。

初始條件

* F[x,y,k]=無窮大
* F[sx,sy,k]=0 ((sx,sy)爲起始點) 

目標結果

* Ans= min { F[tx,ty,k] } ((tx,ty)爲目標點) 

#include <iostream>
#define MAX 101
#define INF 0x7FFFFFFF
using namespace std;

typedef struct
{
    int x,y;
    int d;
}point;

class tQueue
{
public:
    class linklist
    {
    public:
        linklist* next;
        point value;
        linklist()
        {
            next=0;
        }
    };
    linklist *first,*last;
    int size;
    void add(point p)
    {
        if (size==0)
            first=last=new linklist;
        else
            last=last->next=new linklist;
        last->value=p;
        size++;
    }
    point del()
    {
        point rtn=first->value;
        linklist *tfirst=first;
        first=first->next;
        delete tfirst;
        size--;
        return rtn;
    }
    void reset()
    {
        size=0;
        first=last=0;
    }
    tQueue()
    {
        reset();
    }
};

bool balk[MAX][MAX];
int F[MAX][MAX][4]; //0上 1下 2左 3右
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
int N,Ans=INF;
point S,T;
tQueue Q;

void init()
{
    int i,j,k;
    char c;
    freopen("obstacle.in","r",stdin);
    freopen("obstacle.out","w",stdout);
    cin >> N;
    for (i=1;i<=N;i++)
    {
        while ((c=cin.get())==10 || c==13);
        cin.putback(c);
        for (j=1;j<=N;j++)
        {
            c=cin.get();
            if (c=='x')
                balk[i][j]=true;
            if (c=='A')
                S.x=i,S.y=j;
            if (c=='B')
                T.x=i,T.y=j;
            for(k=0;k<4;k++)
                F[i][j][k]=INF;
        }
    }
}

inline bool inrange(point P)
{
    return P.x>=1 && P.x<=N && P.y>=1 && P.y<=N;
}

void bfs()
{
    int k,inc;
    point i,j;
    for (k=0;k<4;k++)
    {
        S.d=k;
        F[S.x][S.y][S.d]=0;
        Q.add(S);
    }
    while (Q.size)
    {
        i=Q.del();
        for (k=0;k<4;k++)
        {
            if (k==i.d)
                inc=0;
            else
                inc=1;
            j.d=k;
            j.x=i.x+dx[k];
            j.y=i.y+dy[k];
            if (inrange(j) && !balk[j.x][j.y])
            {
                if (F[i.x][i.y][i.d] + inc < F[j.x][j.y][k])
                {
                    F[j.x][j.y][k]=F[i.x][i.y][i.d] + inc;
                    if (j.x!=T.x || j.y!=T.y)
                        Q.add(j);
                    else if (F[j.x][j.y][k]<Ans)
                        Ans=F[j.x][j.y][k];
                }
            }
        }
    }
}

int main()
{
    init();
    bfs();
    cout << Ans << endl;
    return 0;
}

<a href="http://cogs.3322.org/wiki/USACOMonthly/2007_10_S/Obstacle_Course/Chinese">障礙訓練場</a>

譯 By BYVoid

考慮一個 N x N (1 <= N <= 100)的有1個個方格組成的正方形牧場。有些方格是奶牛們不能踏上的，它們被標記爲了'x'。例如下圖：

        . . B x .
        . x x A .
        . . . x .
        . x . . .
        . . x . .

貝茜發現自己恰好在點A出，她想去B處的鹽塊添鹽。緩慢而且笨拙的動物，比如奶牛，十分討厭轉彎。儘管如此，當然在必要的時候她們還是會轉彎的。對於一個給定的牧場，請你計算從A到B最少的轉彎次數。開始的時候，貝茜可以使面對任意一個方向。貝茜知道她一定可以到達。

程序名: obstacle

輸入

    * 行 1: 一個整數 N
    * 行 2..N + 1: 行 i+1 有 N 個字符 ('.', 'x', 'A', 'B')，表示每個點的狀態。 

輸出

    * 行 1: 一個整數，最少的轉彎次數。 

輸入樣例

3
.xA
...
Bx.

輸出樣例

2