列印

請 登入 或 註冊帳號.
一小時 一天 一週 一個月 永遠
請輸入帳號, 密碼以及預計登入時間

[sagit]

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;
}

[xavier13540]

我這題是用 DP 解的 設 dp[ i][j][k][l] = 在第 i 行時三部車的所在位置為 j, k, l ( j < k < l ) 的最小油耗
若第 (0, j), (0, k), (0, l) 格皆非障礙物 則 dp[0][j][k][l] = 3 否則為 INF
接著對於三部車子在第 i 行時的所有可能位置 (i, j), (i, k), (i, l) 枚舉所有可能的換車方式 利用 dp[i-1] 算出在該狀態下到達終點的最小油耗
時間複雜度 O(R³C) 對於 R ≦ 10, C ≦ 50 的數據大小而言可以輕鬆解決 我的程式在 ZJ 上的執行時間為 8 ms
以下是我恐怖的程式碼 ( 換車方式太多種了 )

代碼: [選擇]

#include<stdio.h>
#include<algorithm>
#define R 10
#define C 50
#define INF 1000000000
using namespace std;
char map[R][C+1];
int dp[C][R][R][R];
int main(){
    int T,r,c,start[3],start_size;
    scanf("%d",&T);
    while(T--){
        start_size=0;
        scanf("%d%d",&r,&c);
        for(int i=0;i<r;i++){
            scanf("%s",map[i]);
            if(map[i][c-1]=='C')start[start_size++]=i;
        }
        for(int i=0;i<r;i++)for(int j=i+1;j<r;j++)for(int k=j+1;k<r;k++){
            if(map[i][0]!='#'&&map[j][0]!='#'&&map[k][0]!='#')dp[0][i][j][k]=3;
            else dp[0][i][j][k]=INF;
        }
        for(int i=1;i<c;i++)for(int j=0;j<r;j++)for(int k=j+1;k<r;k++)for(int l=k+1;l<r;l++){
            dp[i][j][k][l]=INF;
            if(map[j][i]!='#'&&map[k][i]!='#'&&map[l][i]!='#'){
                if(j>0){
                    dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j-1][k-1][l-1]+6);
                    dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j-1][k-1][l]+5);
                    if(r-l>1)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j-1][k-1][l+1]+6);
                    if(l-k>1)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j-1][k][l-1]+5);
                    dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j-1][k][l]+4);
                    if(r-l>1)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j-1][k][l+1]+5);
                    if(l-k>2)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j-1][k+1][l-1]+6);
                    if(l-k>1)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j-1][k+1][l]+5);
                    if(r-l>1)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j-1][k+1][l+1]+6);
                }
                if(k-j>1){
                    dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j][k-1][l-1]+5);
                    dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j][k-1][l]+4);
                    if(r-l>1)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j][k-1][l+1]+5);
                }
                if(l-k>1)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j][k][l-1]+4);
                dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j][k][l]+3);
                if(r-l>1)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j][k][l+1]+4);
                if(l-k>2)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j][k+1][l-1]+5);
                if(l-k>1)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j][k+1][l]+4);
                if(r-l>1)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j][k+1][l+1]+5);
                if(k-j>2){
                    dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j+1][k-1][l-1]+6);
                    dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j+1][k-1][l]+5);
                    if(r-l>1)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j+1][k-1][l+1]+6);
                }
                if(k-j>1){
                    if(l-k>1)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j+1][k][l-1]+5);
                    dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j+1][k][l]+4);
                    if(r-l>1)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j+1][k][l+1]+5);
                }
                if(l-k>2)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j+1][k+1][l-1]+6);
                if(l-k>1)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j+1][k+1][l]+5);
                if(r-l>1)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j+1][k+1][l+1]+6);
            }
        }
        if(dp[c-1][start[0]][start[1]][start[2]]<INF)printf("%d\n",dp[c-1][start[0]][start[1]][start[2]]);
        else puts("Impossible");
    }
    return 0;
}