USER: tian tianbing [tbbd4261]
TASK: maze1
LANG: C++
Compiling...
Compile: OK
Executing...
Test 1: TEST OK [0.011 secs, 3052 KB]
Test 2: TEST OK [0.000 secs, 3052 KB]
Test 3: TEST OK [0.000 secs, 3052 KB]
Test 4: TEST OK [0.000 secs, 3052 KB]
Test 5: TEST OK [0.011 secs, 3052 KB]
Test 6: TEST OK [0.000 secs, 3088 KB]
Test 7: TEST OK [0.022 secs, 3052 KB]
Test 8: TEST OK [0.000 secs, 3052 KB]
Test 9: TEST OK [0.011 secs, 3052 KB]
Test 10: TEST OK [0.151 secs, 3052 KB]
All tests OK.
Your program ('maze1') produced all correct answers! This is your
submission #2 for this problem. Congratulations!
DFS從兩個入口各搜索一次，更新即可。
先寫了一個代碼，太亂，花了不少時間，后來重寫了，要注意的代碼的整潔。
/*
ID:tbbd4261
PROG:maze1
LANG:C++
*/
#include<fstream>
using namespace std;
ifstream fin("maze1.in");
ofstream fout("maze1.out");
char wall[205][80]={0};
int step[105][40]={0};
char ch;
int x1=0,y1=0,x2=0,y2=0,i,j,w,h;
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
void input()
{
fin>>w>>h;
fin.get();
for(i=1; i<=2*h+1; i++)
{
for(j=1; j<=2*w+1; j++)
{
fin.get(ch); wall[i][j]=ch;
if((i==1||i==2*h+1||j==1||j==2*w+1)&&ch==' ')
{
if(!x1){ x1=i; y1=j; }
else {x2=i; y2=j; }
}
}
fin.get();
}
}
bool valid(int i, int j)
{ return i>=2&&i<=2*h&&j>=2&&j<=2*w&&(i%2==0)&&(j%2==0) ; }
bool valid2(int i, int j){return i>=1&&i<=h&&j>=1&&j<=w; }
void deal(int &x, int &y)
{
for( i=0; i<4; i++ )
if(valid(x+dx[i],y+dy[i]))
{ x=x+dx[i]; y=y+dy[i]; }
x/=2; y/=2;
}
void dfs(int i, int j)
{
for(int k=0; k<4; k++)
if(valid2(i+dx[k],j+dy[k])&&wall[2*i+dx[k]][j*2+dy[k]]==' ')
if((step[i+dx[k]][j+dy[k]]>step[i][j]+1)||step[i+dx[k]][j+dy[k]]==0)
{ step[i+dx[k]][j+dy[k]]=step[i][j]+1; dfs(i+dx[k],j+dy[k]); }
}
int main()
{
input();
deal(x1,y1);
deal(x2,y2);
step[x1][y1]=1;
step[x2][y2]=1;
dfs(x1,y1);
dfs(x2,y2);
int max=1;
for(i=1; i<=h; i++)
for(j=1; j<=w; j++)
if(step[i][j]>max)max=step[i][j];
fout<<max<<endl;
return 0;
}