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