忍者ブログ

Cyber Bird

   

[PR]

×

[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。

2010年予選第8問(AOJ:No.0223)

3日ぶりの更新。部活で演奏会のリハーサルや本番で忙しかったですが、
無事成功しました。

パソコン甲子園昨年の過去問「迷子の双子」です。
問題文・入力例等は、AOJにあるので下のURLからどうぞ。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0223

また、パソコン甲子園公式から過去問とその解説をPDFで見ることもできます。

http://web-ext.u-aizu.ac.jp/pc-concours/2011/03/03_kakomon.html

では、続きからどうぞ。

#include <iostream>
#include <queue>
#include <map>
#define INF	(1<<21)
using namespace std;

typedef pair<int, int> Point;
typedef pair<point, point> PSet;

const int vx[4] = { 1, -1, 0, 0 }, vy[4] = { 0, 0, 1, -1 };
int X, Y;
int maze[50][50];
Point T, K;

bool isBlock( Point t ) {
	int x = t.first, y = t.second;
	if( x < 0 || X <= x || y < 0 || Y <= y ) return true;
	return maze[y][x];
}

int bfs() {
	queue<pset> Q;
	map<pset, int> Time;
	map<pset, bool> M;

	PSet p, q;
	p.first = T; p.second = K;
	Q.push( p );
	Time[p] = 0;
	M[p] = true;
	
	while( !Q.empty() ) {
		p = Q.front(); Q.pop();
		int tx = p.first.first, ty = p.first.second, kx = p.second.first, ky = p.second.second;
		if( tx == kx && ty == ky ) return Time[p];
		if( Time[p] >= 100 ) break;
		
		for( int i = 0; i < 4; i++ ) {
			q.first = Point( tx + vx[i], ty + vy[i] );
			q.second = Point( kx - vx[i], ky - vy[i] );
			if( isBlock( q.first ) ) q.first = Point( tx, ty );
			if( isBlock( q.second ) ) q.second = Point( kx, ky );
			if( !M[q] ) {
				Q.push( q );
				M[q] = true;
				Time[q] = Time[p] + 1;
			}
		}
	}
	
	return INF;
}

main() {
	while( cin >> X >> Y && X && Y ) {
		int tx, ty, kx, ky;
		cin >> tx >> ty >> kx >> ky;
		T.first = tx - 1; T.second = ty - 1;
		K.first = kx - 1; K.second = ky - 1;
		
		for( int i = 0; i < Y; i++ )
			for( int j = 0; j < X; j++ ) cin >> maze[i][j];
		
		int time = bfs();
		if( time != INF ) cout << time << endl;
		else cout << "NA" << endl;
	}
}

今回は時間は計ってないけど、30分以上かかった気がする。
去年参加したときは、本番で幅優先探索も知らずに無謀に挑んでたなあ。
本当に、去年はエラトステネスくらいしか知らないレベルで挑んでいたので
今から考えると時間の無駄だった…

本問は最短時間を求めよとのことなので、幅優先探索で行きましょう。
深さ優先探索はすべてのパターンを試して探索するときに使いますが、
今回は最短のパターンが見つかったらすぐに探索を終了するのでこちらがよいです。

ちなみに、ここまで時間がかかったのは、問題文をちゃんと読んでいなかったから…
時間が100以上かかる時はNAを出力せよと書いてあるのに、
読んでおらず実装していなかった(ソースの36行目)ので、
AOJに2、3回提出してもWAを渡されてまったく原因がわかりませんでしたw
まあ、問題文はちゃんと読めっていう教訓になったのでいいかな。

あと、実際はpairを使わずに、公式の解説のように座標を現在時間とまとめたクラスを作って
キューにぶち込んだ方が速度的には早い気がする…。
このソースでは1250ミリ秒かかってるそうです。
AOJでは制限時間5秒なので問題はなかったですが。
PR

COMMENT

NAME
TITLE
MAIL(非公開)
URL
EMOJI
Vodafone絵文字 i-mode絵文字 Ezweb絵文字
COMMENT
PASS(コメント編集に必須です)
SECRET
管理人のみ閲覧できます

TRACKBACK

Trackback URL:

ブログ内検索

プロフィール

HN:
levelfour
性別:
男性
自己紹介:
ぼちぼち更新を再開する予定です。

twitter

最新コメント

[09/27 菜々氏]
[06/17 NONAME]
[04/30 mithril]
[04/29 Liva]
[01/30 NONAME]

最新トラックバック

コガネモチ

Copyright ©  -- Cyber Bird --  All Rights Reserved
Design by CriCri / Photo by Geralt / powered by NINJA TOOLS / 忍者ブログ / [PR]