Volume 5 / 0515

情報オリンピック 2006予選 解答

Problem 0515 : School Road / 通学経路

高1で習った数学Aにあるような、碁盤目状に繋がっている点間の最短経路の数を求める問題。
深さ優先で解くと時間切れでアウト。
(x,y)までの最短経路の数 = (x-1,y)までの最短経路 + (x,y-1)までの最短経路
が成り立つので幅優先（……だよね？）で解く。

#include <iostream>
#include <vector>
#include <queue>

using namespace std;


void solve( vector< vector<int> > node, int w, int h )
{
	int x, y;
	queue<int> pos_x, pos_y;
	vector< vector<int> > v = node;

	node[1][1] = 1; v[1][1] = -1;
	pos_x.push(2); pos_y.push(1);
	pos_x.push(1); pos_y.push(2);

	while( pos_x.size() > 0 && pos_y.size() > 0 ){
		x = pos_x.front(); y = pos_y.front();
		pos_x.pop(); pos_y.pop();

		if( v[y][x] != -1 ){
			node[y][x] = 0;
			if( node[y-1][x] != -1 ) node[y][x] += node[y-1][x];
			if( node[y][x-1] != -1 ) node[y][x] += node[y][x-1];
			v[y][x] = -1;

			if( x+1 <= w ){
				pos_x.push(x+1); pos_y.push(y);
			}
			if( y+1 <= h ){
				pos_x.push(x); pos_y.push(y+1);
			}
		}
	}

	cout << node[h][w] << endl;

	return;
}

int main(void)
{
	int w, h, x, y, n, i;
	vector< vector<int> > node;

	while( cin >> w >> h, w!=0 && h!= 0 ){
		node.clear(); node.resize( h+2 );
		for( y=0; y<node.size(); y++ )
				node[y].resize( w+2, 0 );

		cin >> n;
		for( i=0; i<n; i++ ){
			cin >> x >> y;
			node[y][x] = -1;
		}

		solve( node, w, h );
	}

	return 0;
}

ちなみに、深さ優先でやったのが次。

// 時間切れでアウト
int solve( vector< vector<bool> > node, int x0, int y0 )
{
	if( x0 == node[0].size()-2 && y0 == node.size()-2 )
		return 1;

	int cnt = 0;

	if( node[y0][x0+1] && x0+1 < node[0].size()-1 )
		cnt += solve( node, x0+1, y0 );
	if( node[y0+1][x0] && y0+1 < node.size()-1 )
		cnt += solve( node, x0, y0+1 );

	return cnt;
}

int main(void)
{
	int w, h, x, y, n, i;
	vector< vector<bool> > node;

	while( cin >> w >> h, w!=0 && h!= 0 ){
		node.clea(); node.resize( h+2 );
		for( y=0; y<node.size(); y++ )
			node[y].resize( w+2, true );

		cin >> n;
		for( i=0; i<n; i++ ){
			cin >> x >> y;
			node[y][x] = false;
		}

		cout << solve( node, 1, 1 ) << endl;
	}

	return 0;
}