Curling 2.0

mike_house

ひさびさに ICPC の問題です.
天下一プログラマーコンテストの問題を解くときに再帰を使ったので,これも再帰で解いてみました.
まだまだだけど,使いこなせるようになればプログラミングの幅も広がるかなと思います.

やってることは,ぶつかる,壊す,直すって感じです.

#include <iostream>
#include <fstream>
#include <vector>
using namespace std;


void
cur(vector<vector<int>> *f, int sx, int sy, int ct, int *mint)	//	t: 滑った回数
{
	//cout << sx << " " << sy << " " << ct << endl;
	//for(unsigned int y = 0; y < f->size(); y++)
	//{
	//	for(unsigned int x = 0; x < f->at(0).size(); x++)
	//	{
	//		cout << f->at(y).at(x) << " ";
	//	}
	//	cout << endl;
	//}

	if(ct > 10)	//	投げる回数は10回まで
	{
		return;
	}

	int d[4][4] = {	//	移動方向
		{0, -1},
		{0, 1},
		{-1, 0},
		{1, 0}
	};

	for(int i = 0; i < 4; i++)
	{
		int x = sx;	//	現在位置
		int y = sy;
		unsigned int nx = x;
		unsigned int ny = y;
		bool f_run = false;	//	移動する前に壁にぶつかるなら動けない
		while(1)
		{
			nx += d[i][0];	//	次の位置
			ny += d[i][1];
			if( nx < 0 || f->at(0).size() <= nx ||	//	枠の外
				ny < 0 || f->size() <= ny)
			{
				break;
			}

			if(f->at(ny).at(nx) == 1)	//	壁に当たる
			{
				if(f_run)
				{
					f->at(ny).at(nx) = 0;
					cur(f, nx-d[i][0], ny-d[i][1], ct+1, mint);
					f->at(ny).at(nx) = 1;	//	元に戻す
				}
				break;
			}
			else if(f->at(ny).at(nx) == 3)	//	ゴール
			{
				if(*mint > ct)
				{
					*mint = ct;
				}
				break;
			}

			f_run = true;
		}
	}

}

int
main(int argc, char** argv)
{
	//	File
	ifstream fin("d.in");
	ofstream fout("d.out");
	
	while(1)
	{
		int w, h;
		fin >> w >> h;
		if(!w || !h)
		{
			break;
		}

		vector<vector<int>> f(h, vector<int>(w));
		int sx, sy;									//	スタート位置
		for(int y = 0; y < h; y++)
		{
			for(int x = 0; x < w; x++)
			{
				int n;
				fin >> n;
				f[y][x] = n;
				if(n == 2)
				{
					sx = x; sy = y;
				}
			}
		}

		int minTimes = INT_MAX;
		int *p_minTimes = &minTimes;
		cur(&f, sx, sy, 1, p_minTimes);

		if(minTimes == INT_MAX)
		{
			fout << -1 << endl;
		}
		else
		{
			fout << minTimes << endl;
		}
	}

	fin.close();
	fout.close();

	return 0;
}