USACO Oct07 Silver 障礙訓練場 obstacle 解題報告

Title: 障礙訓練場

Input: obstacle.in

Output: obstacle.out

Time Limit: 1000 ms

Memory Limit: 128 MB

Level: ★☆

譯 By CmYkRgB123

考慮一個 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

【分析】 

這是一道記憶化搜索題。開一個F[i][j][k]三維數組，記錄奶牛走到(i,j)、方向為k時最少轉彎

次數，除了起點初始化為0外，其他的均初始化為無窮大。

搜索主體是個BFS過程，把起點入隊。每出隊一個元素時，向這個元素的四周擴展，如果能

得到更小的轉彎次數，則更新並入隊。 最後輸出Min{F[X][Y][k]}即可。 X、Y表示終點的

坐標。

我一共提交了兩次，第一次變量名弄錯，WA了24組(！)，只有4分～

第二次AC，但是比較慢，才0.150s，不知道是不是STL queue比較慢。 

【我的代碼】 

裸代碼RawCode

C++语言: Codee#25442

001 /*
002 *Problem: USACO Oct07 Silver obstacle
003 *Author: Yee-fan Zhu
004 *Website: http://zhuyf.tk/
005 */
006 #include <cstdio>
007 #include <cstdlib>
008 #include <cstring>
009 #include <queue>
010 using namespace std;
011 const int MAXN=101;
012 class Point
013 {
014 public:
015     int x,y;
016 }S,E;
017
018 int N;
019 short int Map[MAXN][MAXN];
020 unsigned short int F[MAXN][MAXN][5];
021
022 void init()
023 {
024     scanf("%d\n",&N);
025     char c;
026     for(int i=1;i<=N;i++)
027     {
028         for(int j=1;j<=N;j++)
029         {
030             scanf("%c",&c);
031             while(c!='A' && c!='B' && c!='.' &&
032
033 c!='x')
034                 scanf("%c",&c);
035             if(c=='B')
036                 E.x=i,E.y=j,Map[i][j]=1;
037             if(c=='A')
038                 S.x=i,S.y=j,Map[i][j]=1;
039             if(c=='.')
040                 Map[i][j]=1;
041             if(c=='x')
042                 Map[i][j]=0;
043             for(int k=1;k<=4;k++)
044                 F[i][j][k]=10000;
045         }
046     }
047 }
048
049 class QUEUE
050 {
051 public:
052     int x,y,tm;
053 };
054 queue<QUEUE>Q;
055 const int step[5][2]={{0,0},{0,1},{0,-1},{1,0},{-1,0}};
056
057 void bfs()
058 {
059     for(int i=1;i<=4;i++)
060         F[S.x][S.y][i]=0;
061     QUEUE tmp,nxt;
062    
063     for(int i=1;i<=4;i++)
064     {
065         tmp.x=S.x,tmp.y=S.y,tmp.tm=i;
066         Q.push(tmp);
067     }
068    
069     int tx,ty,tt,tf;
070     int nx,ny,nf;
071     while(!Q.empty())
072     {
073         tmp=Q.front();
074         Q.pop();
075         tx=tmp.x,ty=tmp.y,tt=tmp.tm,tf=F[tx][ty][tt];
076         for(int i=1;i<=4;i++)
077         {
078             nx=tx+step[i][0];
079             ny=ty+step[i][1];
080             if(i==tt)
081                 nf=tf;
082             if(i!=tt)
083                 nf=tf+1;
084             if(nx>N || nx<1 || ny>N || ny<1)
085                 continue;
086             if(Map[nx][ny]==0)
087                 continue;
088             if(F[nx][ny][i]<=nf)
089                 continue;
090             F[nx][ny][i]=nf;
091             nxt.x=nx,nxt.y=ny,nxt.tm=i;
092             Q.push(nxt);
093         }
094     }
095     int Min=10000000;
096     for(int i=1;i<=4;i++)
097         if(F[E.x][E.y][i]<Min)
098             Min=F[E.x][E.y][i];
099     printf("%d\n",Min);
100 }
101
102 int main()
103 {
104     freopen("obstacle.in","r",stdin);
105     freopen("obstacle.out","w",stdout);
106     init();
107     bfs();
108     return 0;
109 }