记忆化广度优先搜索，或者动态规划。

状态设定

* 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