比赛 |
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;
}