USACO 5.2.1 Snail Trails 蝸牛的旅行 snail

本文正體字版由OpenCC轉換

一道簡單的題，模擬蝸牛走的路線，深搜，計算走的最多步數即可。

注意題目中說的“當 N 〉26 時，輸入文件就不能表示 Z 列以後的路障了”，這句話不用專門理他。其實就是從A的ascii碼開始向後順延，不管是什麼字母就行了。

<pre><span>USER: CmYkRgB123 CmYkRgB123 [cmykrgb1]
TASK: snail
LANG: C++

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.000 secs, 2856 KB]
   Test 2: TEST OK [0.000 secs, 2852 KB]
   Test 3: TEST OK [0.000 secs, 2856 KB]
   Test 4: TEST OK [0.022 secs, 2852 KB]
   Test 5: TEST OK [0.011 secs, 2856 KB]
   Test 6: TEST OK [0.011 secs, 2852 KB]
   Test 7: TEST OK [0.000 secs, 2856 KB]
   Test 8: TEST OK [0.000 secs, 2852 KB]
   Test 9: TEST OK [0.000 secs, 2856 KB]
   Test 10: TEST OK [0.000 secs, 2856 KB]
   Test 11: TEST OK [0.011 secs, 2852 KB]
   Test 12: TEST OK [0.032 secs, 2856 KB]

All tests OK.
</span>
<span>Your program ('snail') produced all correct answers!  This is your
submission #2 for this problem.  <strong>Congratulations!</strong>
</span>
</pre>

/*
ID: cmykrgb1
PROG: snail
LANG: C++
*/

#include <iostream>
#include <fstream>
#define MAX 121

using namespace std;

ifstream fi("snail.in");
ofstream fo("snail.out");

char M[MAX][MAX];
int maxstep=0;
int N,B;

void init()
{
	int i,b;
	char a;
	fi >> N >> B;
	for (i=1;i<=B;i++)
	{
		b=fi.get();
		fi >> a >> b;
		a-='A'-1;
		M[a][b]='#';
	}
}

int max(int a,int b)
{
	return a>b?a:b;
}

void dfs(int x,int y,int step)
{
	int dx,dy;
	bool r;

	for (dx=x+1,dy=y,r=false;dx<=N;dx++) //右
	{
		if (M[dx][dy]=='#')
			break;
		if (M[dx][dy]==1)
		{
			maxstep=max(maxstep,step+dx-x);
			r=true;
			break;
		}
		M[dx][dy]=1;
	}
	dx--;
	if(!r && !(dx==x && dy==y)) dfs(dx,dy,step+dx-x);
	for (;dx>=x+1;dx--)
		M[dx][dy]=0;

	for (dx=x-1,dy=y,r=false;dx>=1;dx--) //左
	{
		if (M[dx][dy]=='#')
			break;
		if (M[dx][dy]==1)
		{
			maxstep=max(maxstep,step+x-dx);
			r=true;
			break;
		}
		M[dx][dy]=1;
	}
	dx++;
	if(!r && !(dx==x && dy==y)) dfs(dx,dy,step+x-dx);
	for (;dx<=x-1;dx++)
		M[dx][dy]=0;

	for (dx=x,dy=y+1,r=false;dy<=N;dy++) //下
	{
		if (M[dx][dy]=='#')
			break;
		if (M[dx][dy]==1)
		{
			maxstep=max(maxstep,step+dy-y);
			r=true;
			break;
		}
		M[dx][dy]=1;
	}
	dy--;
	if(!r && !(dx==x && dy==y)) dfs(dx,dy,step+dy-y);
	for (;dy>=y+1;dy--)
		M[dx][dy]=0;

	for (dx=x,dy=y-1,r=false;dy>=1;dy--) //上
	{
		if (M[dx][dy]=='#')
			break;
		if (M[dx][dy]==1)
		{
			maxstep=max(maxstep,step+y-dy);
			r=true;
			break;
		}
		M[dx][dy]=1;
	}
	dy++;
	if(!r && !(dx==x && dy==y)) dfs(dx,dy,step+y-dy);
	for (;dy<=y-1;dy++)
		M[dx][dy]=0;
}

void print()
{
	fo << maxstep << endl;
	fi.close();
	fo.close();
}

int main()
{
	init();
	M[1][1]=1;
	dfs(1,1,0);
	print();
	return 0;
}

上次修改時間 2017-05-22

相關日誌