比赛 20101224 评测结果 WWWWWWWWWW
题目名称 激光电话 最终得分 0
用户昵称 Citron酱 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2010-12-24 21:08:28
显示代码纯文本
#include <fstream>

#define I_F "lphone.in"
#define O_F "lphone.out"
#define MAX 100

using namespace std;

short n,m;
short x1,x2,yy,y2;
int ans;
bool map[MAX][MAX];
int nim[MAX][MAX];
short sign[MAX][MAX];

const short r1[4]={0,1,-1,0};
const short r2[4]={1,0,0,-1};

void Input();
void Dfs(short x, short y);
void Output();

int main()
{
	Input();
	Dfs(x1,yy);
	Output();
	return 0;
}

void Input()
{
	ifstream fin(I_F);
	fin>>n>>m;
	char t;
	bool f=false;
	short i,j;
	for (i=0; i<n; i++)
		for (j=0; j<n; j++)
		{
			fin>>t;
			if (t=='.')
				map[i][j]=true;
			else if (t=='#')
				map[i][j]=false;
			else
			{
				map[i][j]=true;
				if (f)
				{
					x2=i;
					y2=j;
				}
				else
				{
					x1=i;
					yy=j;
				}
			}
		}
	fin.close();
}

void Dfs(short x, short y)
{
	if ((x==x2)&&(y==y2))
		return;
	short i;
	if ((x==x1)&&(y==y2))
	{
		for (i=0; i<4; i++)
			if (map[x+r1[i]][y+r2[i]]&&(x+r1[i]>=0)&&(x+r1[i]<n)&&(y+r2[i]<m)&&(y+r2[i]>=0))
			{
				sign[x+r1[i]][y+r2[i]]=i+1;
				Dfs(x+r1[i],y+r2[i]);
			}
	}
	else
		for (i=0; i<4; i++)
			if (map[x+r1[i]][y+r2[i]]&&(i+sign[x][y]!=4)&&(x+r1[i]>=0)&&(x+r1[i]<n)&&(y+r2[i]<m)&&(y+r2[i]>=0)&&((y+r2[i]!=yy)||(x+r1[i]!=x1))&&((i+1==sign[x][y])||(nim[x+r1[i]][y+r2[i]]>nim[x][y])))
			{
				sign[x+r1[i]][y+r2[i]]=i+1;
				if (sign[x][y]!=i+1)
					nim[x+r1[i]][y+r2[i]]=nim[x][y]+1;
				else
					nim[x+r1[i]][y+r2[i]]=nim[x][y];
				Dfs(x+r1[i],y+r2[i]);
			}
}

void Output()
{
	ofstream fout(O_F);
	fout<<nim[x2][y2]<<'\n';
	fout.close();
}