USACO chapter 2 section 2.4 Overfencing

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

posted on 2010-08-03 10:41 田兵 阅读(115) 评论(0)  编辑 收藏 引用 所属分类: USACO


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2010年8月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
2930311234

导航

统计

常用链接

留言簿(2)

随笔分类(65)

随笔档案(65)

文章档案(2)

ACM

搜索

积分与排名

最新随笔

最新评论

阅读排行榜