[記憶化搜索]USACO Jan09 Silver Laserphones 激光電話

**********************************************************************

Problem 8: Laserphones [Rob Kolstad, 2008]

The cows have a new laser-based system so they can have casual
conversations while out in the pasture which is modeled as a W x H
grid of points (1 <= W <= 100; 1 <= H <= 100).

The system requires a sort of line-of-sight connectivity in order
to sustain communication. The pasture, of course, has rocks and
trees that disrupt the communication but the cows have purchased
diagonal mirrors ('/' and '\' below) that deflect the laser beam
through a 90 degree turn. Below is a map that illustrates the
problem.



H is 8 and W is 7 for this map.  The two communicating cows are
notated as 'C's; rocks and other blocking elements are notated as
'*'s:

7 . . . . . . .         7 . . . . . . .
6 . . . . . . C         6 . . . . . /-C
5 . . . . . . *         5 . . . . . | *
4 * * * * * . *         4 * * * * * | *
3 . . . . * . .         3 . . . . * | .
2 . . . . * . .         2 . . . . * | .
1 . C . . * . .         1 . C . . * | .
0 . . . . . . .         0 . \-------/ .
  0 1 2 3 4 5 6           0 1 2 3 4 5 6

Determine the minimum number of mirrors M that must be installed
to maintain laser communication between the two cows, a feat which
is always possible in the given test data.

PROBLEM NAME: lphone

INPUT FORMAT:

* Line 1: Two space separated integers: W and H

* Lines 2..H+1: The entire pasture.

SAMPLE INPUT (file lphone.in):

7 8
.......
......C
......*
*****.*
....*..
....*..
.C..*..
.......

OUTPUT FORMAT:

* Line 1: A single integer: M

SAMPLE OUTPUT (file lphone.out):

3

**********************************************************************

【分析】
和USACO Oct07 obstacle一模一樣啊，就是求最少轉幾次彎，方法是記憶化搜索或動態規劃。詳細的我就不寫了，直接看USACO Oct07 obstacle吧。
我在這道題中，加了一個obstacle中沒有的優化，就是禁止反向走，因為180度掉頭反向走根本無法取得最優解。
比如有一個丁字路口，在橫穿馬路前向左轉彎和橫穿馬路後掉頭向後轉再向右轉彎的實際效果一樣，但是後者要比前者多轉一次彎，所以掉頭就不必考慮了，這可以節省出很多的時間。

PS:
1.題目又是RK出的，好親切啊～
2.Windows 7的寫字板是個好東西，把樣例粘貼進去就有效果了（微軟雅黑字體不行哦）

有圖有真相

3.我的程序效率可是真高啊，有圖為證：

跟別人聊著天，還能寫出一次AC且急速的程序，令我汗顏啊，一心真的可以二用。

不扯淡了，Code！

【我的代碼】
裸代碼RawCode

C++语言: Codee#25462

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