USACO Section 2.4 Overfencing - 略坑爹的输入..再一个函数递归来DFS要慎用.

题目很简单了..从每个出口做一次搜索~~边遍历边判断更新赋值...最后扫描一次全图..找到值最大了就是答案了...

这个输入阿~~会有多余的空格~~也会有本来是一行都是空的~~结果打了两个空格就换行了~~~坑爹啊~~输入的时候又不能用gets...getline不知道用...就各种判断硬是用scanf完成了输入...

还有开始时用函数递归来DFS...结果超时了~~似乎是跑了1.6s还没出来...后来改成自己写队列BFS...结果全部都0,00s过...呃....好吧..有时候还是不能图方便...

Program:

/*  
ID: zzyzzy12  
LANG: C++  
TASK: maze1
*/    
#include<iostream>    
#include<istream>
#include<stdio.h>    
#include<string.h>    
#include<math.h>    
#include<stack>
#include<algorithm>    
#include<queue> 
using namespace std;     
int W,H,i,j,x,y,ans[305][305];
char mar[305][305],c; 
struct node
{
     int y,x;      
};
queue<node> myqueue;
void getanswer(int y,int x)
{ 
     node h,k;
     ans[y][x]=1;
     h.x=x; h.y=y; myqueue.push(h);
     while (!myqueue.empty())
     {
           h=myqueue.front();
           myqueue.pop();
           x=h.x; y=h.y;
           if (x!=1 && mar[y][x-1]==' ' && ans[y][x-2]>ans[y][x]+1) 
           {
                 k.y=y; k.x=x-2; ans[y][x-2]=ans[y][x]+1;
                 myqueue.push(k);
           }
           if (x!=2*W-1 && mar[y][x+1]==' ' && ans[y][x+2]>ans[y][x]+1) 
           {
                 k.y=y; k.x=x+2; ans[y][x+2]=ans[y][x]+1;
                 myqueue.push(k);                        
           }
           if (y!=1 && mar[y-1][x]==' ' && ans[y-2][x]>ans[y][x]+1)
           {
                 k.y=y-2; k.x=x; ans[y-2][x]=ans[y][x]+1;
                 myqueue.push(k);                    
           }
           if (y!=2*H-1 && mar[y+1][x]==' ' && ans[y+2][x]>ans[y][x]+1)
           {
                 k.y=y+2; k.x=x; ans[y+2][x]=ans[y][x]+1;
                 myqueue.push(k);                        
           }
     }
     return;
}
int main()
{
     freopen("maze1.in","r",stdin);  
     freopen("maze1.out","w",stdout);  
     scanf("%d%d",&W,&H); c=' ';
     for (i=0;i<=2*H;i++)
     { 
           while (c!='\n' && c!='\0') scanf("%c",&c);
           c=' ';
           for (j=0;j<=2*W;j++) 
           {
                scanf("%c",&mar[i][j]); 
                if (mar[i][j]=='\n') { c=='\n'; break; }
           }
           for (;j<=2*W;j++) mar[i][j]=' ';  
     }
     while (!myqueue.empty()) myqueue.pop();
     memset(ans,0x7F,sizeof(ans));
     for (y=0;y<=2*H;y++) 
     {
           if (mar[y][0]==' ' && ans[y][1]>1) getanswer(y,1);  
           if (mar[y][2*W]==' ' && ans[y][2*W-1]>1) getanswer(y,2*W-1); 
     }
     for (x=0;x<=2*W;x++)
     {
           if (mar[0][x]==' ' && ans[1][x]>1) getanswer(1,x);  
           if (mar[2*H][x]==' ' && ans[2*H-1][x]>1) getanswer(2*H-1,x);          
     }
     int m=0;
     for (y=1;y<2*H;y+=2)
        for (x=1;x<2*W;x+=2)
           if (m<ans[y][x]) m=ans[y][x];
     printf("%d\n",m);
     return 0;   
}