比赛 20130729 评测结果 AATTTTTTTT
题目名称 激光电话 最终得分 20
用户昵称 slyrabbit 运行时间 8.011 s
代码语言 C++ 内存使用 0.56 MiB
提交时间 2014-07-17 09:10:03
显示代码纯文本
#include<iostream>
#include<cstdio>
using namespace std;
int w,h,s=100000,istart,jstart,ians,jans;
int b[110][110][5]={0};
char a[110][110];
int r1[5]={0,-1,0,1,0},r2[5]={0,0,-1,0,1};
void init()
{
	cin>>w>>h;
	bool t=false;
	for(int i=1;i<=h;i++)
	{
		for(int j=1;j<=w;j++)
		{
			cin>>a[i][j];
			if(a[i][j]=='C')
			{
				if(t==false)
				{
					t=true;
					istart=i;
					jstart=j;
				}
				else
				{
					ians=i;
					jans=j;
				}
			}
		}
	}
}
void dfs(int i,int j,int n,int d)
{
	if(i==ians&&j==jans)
	{
		if(s>n)
			s=n;
		return;
	}
	if(a[i][j]!='.'&&a[i][j]!='C')
		return;
	if((a[i-1][j]=='@'&&a[i][j-1]=='@')||(a[i-1][j]=='@'&&a[i][j+1]=='@')||(a[i+1][j]=='@'&&a[i][j-1]=='@'||a[i+1][j]=='@'&&a[i][j+1]=='@'))
		return;
	for(int k=1;k<=4;k++)
	{
		int temp=n;
		if(k%2!=d%2&&d!=0)
			temp+=1;
		a[i][j]='@';
		dfs(i+r1[k],j+r2[k],temp,k);
		a[i][j]='.';
	}
}
int main()
{
	freopen("lphone.in","r",stdin);
	freopen("lphone.out","w",stdout);
	init();
	dfs(istart,jstart,0,0);
	cout<<s;
	return 0;
}