NPSC 2009 高中組 初賽 D.賽車
說明:給你一個 RxC 的地圖,在最右邊有三個物體,同時向左邊移動,往正左方移動一格的花費是1、往左上或左下移動一格的花費則是2,請問你到達畫面最左邊的最小花費是多少。如果因為障礙物而三個物體無法同時移動,則輸出Impossible。
測資範圍:R<=10、C<=50
解法:狀態空間搜尋+Branch and Bound。將三個物體的位置視為一個狀態,計算目前為止的花費以及預估到終點的最小花費,將這些狀態丟進一個優先權佇列(Priority Queue),並以預估總花費最小的優先取出進行BFS搜尋,即可找到答案。為了避免同樣的狀態重覆展開,我們用 V 陣列記錄每個狀態目前為止最小的花費,如果沒有比它小,則不再展開。
參考程式:(By sagit)
// NPSC 2009 高中組 初賽
// D.賽車
// By sagit
// 狀態空間搜尋、Branch and Bound
#include <cstdlib>
#include <iostream>
#include <queue>
using namespace std;
const short int R=10, C=50, MAX=500, DX=27;
char Map[R][C];
short int V[C][R][R][R], r, c;
struct X { short int r[3], c, gx, fx; };
// r[] 車子所在的列, c 車子所在的行, gx 目前的花費, fx 預估最小總花費
bool operator< ( const X& a , const X& b ) // 比較函數
{ if (a.fx>b.fx) return 1; if (a.fx<b.fx) return 0; return (a.c>b.c); }
short int dx[DX][4]={ {0, 0, 0, 3}, {1, 0, 0, 4}, {0, 1, 0, 4}, {0, 0, 1, 4},
{-1, 0, 0, 4}, {0, -1, 0, 4}, {0, 0, -1, 4}, {1, 1, 0, 5},
{-1, 1, 0, 5}, {1, -1, 0, 5}, {-1, -1, 0, 5}, {1, 0, 1, 5},
{-1, 0, 1, 5}, {1, 0, -1, 5}, {-1, 0, -1, 5}, {0, 1, 1, 5},
{0, -1, 1, 5}, {0, 1, -1, 5}, {0, -1, -1, 5}, {1, 1, 1, 6},
{-1, 1, 1, 6}, {1, -1, 1, 6}, {1, 1, -1, 6}, {-1, -1, 1, 6},
{-1, 1, -1, 6}, {1, -1, -1, 6}, {-1, -1, -1, 6} };
int main(int argc, char *argv[])
{
short int z, i, j, k, l, best;
char ch;
X a, b;
freopen("pd.in", "rt", stdin);
freopen("pd.out", "w+t", stdout);
ios_base::sync_with_stdio(false);
cin >> z;
while (z--)
{
cin >> r >> c;
for (i=0, k=0; i<r; i++) // 輸入地圖
for (j=0; j<c; j++)
{
cin >> ch;
Map[i][j]= ( (ch=='#') ? 1 : 0 );
if (ch=='C') a.r[k++]=i; // 記錄車子的啟始位置
}
if (c==1)
{
cout << 3 << endl;
continue;
}
for (i=0; i<c; i++)
for (j=0; j<r; j++)
for (k=0; k<r; k++)
for (l=0; l<r; l++)
V[i][j][k][l]=MAX;
a.c=c-1;
a.gx=3;
a.fx=c*3;
priority_queue<X> PQ;
PQ.push(a);
best=MAX;
while ( !PQ.empty() ) // BFS
{
a=PQ.top();
PQ.pop();
if (a.fx>=best) break;
l=(a.r[2]*100+a.r[1]*10+a.r[0])+(1000*a.c);
k=a.c-1;
for (i=0; i<DX; i++)
{
b.r[0]=a.r[0]+dx[i][0];
b.r[1]=a.r[1]+dx[i][1];
b.r[2]=a.r[2]+dx[i][2];
if ( b.r[0]<0 || b.r[2]>=r || b.r[0]>=b.r[1] ||
b.r[1]>=b.r[2] || Map[b.r[0]][k] ||
Map[b.r[1]][k] || Map[b.r[2]][k] ) continue;
b.c=k;
b.gx=a.gx+dx[i][3];
b.fx=b.gx+k*3;
if ( b.fx>=best || b.fx>=V[b.c][b.r[0]][b.r[1]][b.r[2]] )
continue;
V[b.c][b.r[0]][b.r[1]][b.r[2]]=b.fx;
if (k) PQ.push(b);
else if (b.gx<best) best=b.gx; // 到達終點
}
}
if (best==MAX) cout << "Impossible" << endl;
else cout << best << endl;
}
// system("PAUSE");
return EXIT_SUCCESS;
}