スポンサーサイト

--.--.-- --:--  スポンサー広告

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

| - | - | ↑ページトップ |




11パズル

2008.11.21 14:04  パソコン甲子園 2008

問題 パソコン甲子園2008 08

下図のような11パズルを解く最短の手数を求めよ。ただし、20手以内で解けない場合はNAと出力する。

11パズル
入力例
2
1 0 3
4 5 6 7 8
9 0 11
10
0
1 2 3
4 5 6 7 8
9 10 11
0
0
11 10 9
8 7 6 5 4
3 2 1
0
-1

出力例
2
0
NA


解説

幅優先探索では「時間切れ」になってしまいます。
この問題は、両側探索または反復深化等のヒューリスティックを用いた探索でなければ解けません。以下は、反復深化による解法です。

サンプルプログラム

#include
#include

using namespace std;

#define N 5
#define REP(i, n) for ( int i = 0; i < (int)n; i++ )
#define LIMIT 20

static const int T[12][2] = {{-1, -1}, {1, 1}, {1, 2}, {1, 3}, {2, 0}, {2, 1},
			     {2, 2}, {2, 3}, {2, 4}, {3, 1}, {3, 2}, {3, 3}};
static const int g[N][N] = {{-1, -1, 0, -1, -1}, {-1, 1, 2, 3, -1},
			    {4, 5, 6, 7, 8}, {-1, 9, 10, 11, -1}, {-1, -1, 0, -1, -1}};

class Puzzle{
    public:
    int C[N][N], mdist; //manhatta distance
    Puzzle(){}

    bool swapAdj( int si, int sj, int ti, int tj ){
	if ( ti < 0 || tj < 0 || ti >= N || tj >= N ) return false;
	if ( C[ti][tj] <= 0 ) return false;
	swap(C[ti][tj], C[si][sj]);
	int tti = T[C[si][sj]][0];
	int ttj = T[C[si][sj]][1];
	mdist -= max(tti, ti)-min(tti, ti) + max(ttj, tj)-min(ttj, tj);
	mdist += max(tti, si)-min(tti, si) + max(ttj, sj)-min(ttj, sj);
	return true;
    }

    bool isGoal(){
	REP(i, N) REP(j, N) if ( g[i][j] != C[i][j] ) return false;
	return true;
    }

    int getMD(){ // get initial manhattan distance
	int sum = 0;
	int ti, tj;
	REP(i, 5) REP(j, 5){
	    if ( C[i][j] <= 0 ) continue;
	    ti = T[C[i][j]][0];
	    tj = T[C[i][j]][1];
	    sum += (max(ti, i)-min(ti, i) + max(tj, j) - min(tj, j));
	}
	return sum;
    }
};

int limit;

bool dfs( int depth, Puzzle P ){
    if ( P.isGoal() ) return true;
    if ( depth + P.getMD() > limit ) return false;

    static const int di[4] = {0, -1, 0, 1};
    static const int dj[4] = {1, 0, -1, 0};

    REP(i, N) REP(j, N){
	if ( P.C[i][j] != 0 ) continue;
	REP(r, 4){
	    Puzzle v = P;
	    if ( !v.swapAdj(i, j, i+di[r], j+dj[r]) ) continue;
	    if ( dfs( depth + 1, v ) ) return true;
	}
    }

    return false;
}

int idp(Puzzle source){
    for ( limit = 0; limit <= LIMIT; limit++ ){
	source.mdist = source.getMD();
	if ( dfs(0, source) ) return limit;
    }
    return INT_MAX;
}

int main(){
    Puzzle P;
    int top;

    while(1){
	cin >> top;
	if ( top == -1 ) break;
	REP(j, N) P.C[0][j] = -1;
	P.C[0][2] = top;
	for(int i = 1; i < N; i++) REP(j, N){
	    if ( (i == 1 || i == 3) && (j == 0 || j == 4 ) ) P.C[i][j] = -1;
	    else if ( i == 4 && j != 2 ) P.C[i][j] = -1;
	    else cin >> P.C[i][j];
	}

	int cost = idp(P);
	if ( cost == INT_MAX ) cout << "NA" << endl;
	else cout << cost << endl;	
    }

    return 0;
}

スポンサーサイト

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |




白虎運送

2008.11.19 09:49  パソコン甲子園 2008

問題 パソコン甲子園2008 12

下図に示すように、M本の東西方向の道路、N本の南北の道路からなる格子状の地図において、トラックが始点の交差点から終点の交差点までたどり着くまでの最短時間を求めよ。

白虎運送
トラックは東西南北方向の交差点に進入できるが、来た方向へはUターンできない。さらに、交差点には信号機がある所があり、各信号機のシグナルは一定の周期で東西ー南北方向に切り替わる(赤と青のみ)。交差点に進入できるのは進行方向の信号機が青の場合である。また、交差点から隣の交差点への移動には一定の時間D分を要するが、渋滞の道路ではさらにd分要する。工事中で通れない道路もある。

N, M <= 20 であり、トラックは100分以内で目的地に到達できるものとする。


解説

最短経路問題なので、ダイクストラのアルゴリズムで解けそうですが、この問題の場合、以下のような状態空間を定義すれば、深さ優先探索で解くことができます。

V[y][x][t][d]: dの方向から交差点(y, x)に時刻tで到達することができれば、V[y][x][t][d] がtrueであるような4次元配列

トラックは100分以内で目的地に到達できるので、t <= 100 であり、メモリも間に合います。
目的地の座標 (y, x) について、Vの値が最初に true となる t の値が答えになります。

サンプルプログラム

001 #include<iostream>
002 using namespace std;
003 
004 #define REP(i, n) for ( int i = 0; i < (int)n; i++ )
005 #define GMAX 20
006 #define TMAX 100
007 #define INFTY (1<<21)
008 
009 int N, M, D, sy, sx, gy, gx;
010 int G[GMAX][GMAX][GMAX][GMAX], S[GMAX][GMAX];
011 bool V[GMAX][GMAX][TMAX+1][4];
012 
013 static const int dy[4] = {0, -1, 0, 1};
014 static const int dx[4] = {1, 0, -1, 0};
015 
016 bool valid( int y , int x ){
017     return ( 0 <= y && 0 <= x && y < N && x < M );
018 }
019 
020 void dfs( int y, int x, int t, int d ){
021     V[y][x][t][d] = true;
022     
023     int ny, nx, nt;
024     for ( int nd = 0; nd < 4; nd++ ){
025         if ( (d+2)%4 == nd ) continue;
026         
027         ny = y + dy[nd];
028         nx = x + dx[nd];
029         
030         if ( !valid(ny, nx) ) continue;
031         if ( G[y][x][ny][nx] == INFTY ) continue;
032         
033         nt = t + G[y][x][ny][nx];
034         
035         if ( nt > TMAX ) continue;
036         
037         if ( S[ny][nx] > 0 ){
038             if ( nd % 2 == 0 ){
039                 if ( (nt/S[ny][nx])%2 != 1 ) continue;
040             } else {
041                 if ( (nt/S[ny][nx])%2 != 0 ) continue;
042             }
043         }
044         
045         if ( V[ny][nx][nt][nd] ) continue;
046         
047         dfs( ny, nx, nt, nd );
048     }
049 }
050 
051 int compute(){
052     REP(y, N) REP(x, M) REP(t, TMAX+1) REP(d, 4) V[y][x][t][d] = false;
053     REP(d, 4) dfs( sy, sx, 0, d );
054     
055     REP(t, TMAX+1) REP(d, 4) if ( V[gy][gx][t][d] ) return t;
056 }
057 
058 int getNumber( char ch ){ return ch - 'a';}
059 
060 bool input(){
061     cin >> N >> M;
062     if ( N == 0 && M == 0 ) return false;
063     cin >> D;
064     
065     int ny, nx;
066     REP(y, N) REP(x, M){
067         S[y][x] = 0;
068         REP(nd, 4){
069             ny = y + dy[nd];
070             nx = x + dx[nd];
071             if ( valid(ny, nx) ){
072                 G[y][x][ny][nx] = G[ny][nx][y][x] = D;
073             }
074         }
075     }
076     
077     int nsignal, nconst, njam, y1, x1, y2, x2, k, d;
078     char ch, tmp;
079     
080     cin >> nsignal;
081     for ( int i = 0; i < nsignal; i++ ){
082         cin >> ch  >> tmp >> x1 >> k; x1--;
083         S[getNumber(ch)][x1] = k;
084     }
085     
086     cin >> nconst;
087     for ( int i = 0; i < nconst; i++ ){
088         cin >> ch >> tmp >> x1; x1--;
089         y1 = getNumber(ch);
090         cin >> ch >> tmp >> x2; x2--;
091         y2 = getNumber(ch);
092         G[y1][x1][y2][x2] = G[y2][x2][y1][x1] = INFTY;
093     }
094     
095     cin >> njam;
096     for ( int i = 0; i < njam; i++ ){
097         cin >> ch >> tmp >> x1; x1--;
098         y1 = getNumber(ch);
099         cin >> ch >> tmp >> x2 >> d; x2--;
100         y2 = getNumber(ch);
101         G[y1][x1][y2][x2] += d;
102         G[y2][x2][y1][x1] += d;
103     }
104     
105     cin >> ch >> tmp >> sx; sy = getNumber(ch);
106     cin >> ch >> tmp >> gx; gy = getNumber(ch);
107     sx--; gx--;
108     return true;
109 }
110 
111 int main(){
112     while( input() ) cout << compute() << endl;
113     return 0;
114 }

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |




パソコン甲子園2008

2008.11.19 09:33  パソコン甲子園 2008

パソコン甲子園2008本線問題

番号問題難易度点数
01 三目並べ 30
02 鶴ヶ城 20
03 ゴールドバッハ予想 20
04 会津地鶏 ★☆ 20
05 投石おみくじ ★★ 20
06 探索 40
07 便利なのはどこ? ★★☆ 40
08 11パズル ★★★☆ 70
09 おおきくなあれ ★★★ 70
10 鶴ヶ城駐車場 ★★★ 90
11 デブンイレブン ★★★ 90
12 白虎運送 ★★★☆ 90


テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。