记录编号	120810	评测结果	AAAAAAAAAA
题目名称	穿越栅栏	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	0.053 s
提交时间	2014-09-16 20:52:23	内存使用	0.43 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <iterator>
#include <functional>
#define pritnf printf
#define scafn scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
using namespace std;
typedef long long LL;
typedef unsigned int Uint; 
const int INF=0x7ffffff;
//==============struct declaration==============
struct node
{
  int nr,nc;
  node (int nr=0,int nc=0):nr(nr),nc(nc){};
} ;
//==============var declaration=================
#define map maps
char map[250][250];
int dist[200][150];
int r1=-1,r2=-1,c1,c2,row,col;
bool visable[110][110][4];//上右下左
int mvr[]={-1,0,1,0};
int mvc[]={0,1,0,-1};
queue <node> Q; 
//==============function declaration============

//==============main code=======================
int main()
{  
  string FileName="maze1";//程序名 
  string FloderName="COGS";//文件夹名 
  freopen((FileName+".in").c_str(),"r",stdin);
  freopen((FileName+".out").c_str(),"w",stdout);
#ifdef DEBUG  
  system(("cp C:\\Users\\Administrator\\Desktop\\"+FloderName+"\\standard.cpp C:\\Users\\Administrator\\Desktop\\"+FloderName+"\\submit.txt").c_str());
  clock_t Start_Time=clock();
#endif    
  scanf("%d%d",&col,&row);
  cin.ignore(10,10);
  For(i,0,row*2+1)
    cin.getline(map[i],1000);
  /*For(i,0,row*2+1)
    pritnf("%s\n",map[i]);*/
  memset(visable,false,sizeof(false));
  for(int rr=1;rr<row*2+1;rr+=2)
    for(int cc=1;cc<col*2+1;cc+=2)
    {
      int r=rr/2+1;
      int c=cc/2+1;
      //上右下左 
      if (map[rr-1][cc]==' ')
        visable[r][c][0]=true;
      if (map[rr][cc+1]==' ')
        visable[r][c][1]=true;
      if (map[rr+1][cc]==' ')
        visable[r][c][2]=true;
      if (map[rr][cc-1]==' ')
        visable[r][c][3]=true;
    }
  For(i,1,col)
  {
    if (visable[1][i][0])
    {
      visable[1][i][0]=false;
      if (r1==-1)
        r1=1,c1=i;
      else
      {
        r2=1;c2=i;
        goto OUT__;
      }
    }
    if (visable[row][i][2])
    {
      visable[row][i][2]=false;
      if (r1==-1)
        r1=row,c1=i;
      else
      {
        r2=row;c2=i;
        goto OUT__;
      }
    }
  }
  For(i,1,row)
  {
    if (visable[i][1][3])
    {
      visable[i][1][3]=false;
      if (r1==-1)
        r1=i,c1=1;
      else
      {
        r2=i;c2=1;
        goto OUT__;
      }
    }
    if (visable[i][col][1])
    {
      visable[i][col][1]=false;
      if (r1==-1)
        r1=i,c1=col;
      else
      {
        r2=i;c2=col;
        goto OUT__;
      }
    }
  }
  OUT__:
  memset(dist,-1,sizeof(dist));
  dist[r1][c1]=dist[r2][c2]=1;
  /*pritnf("%d %d %d %d\n",r1,c1,r2,c2);
  return 0;*/
  Q.push(node(r1,c1));Q.push(node(r2,c2));
  int ans=-1;
  while (!Q.empty())
  {
    node now=Q.front();Q.pop();
    ans=max(ans,dist[now.nr][now.nc]);
    For(i,0,3)
    {
      int rr=now.nr+mvr[i],cc=now.nc+mvc[i];
      if (rr<1||rr>row||cc<1||cc>col||(!visable[now.nr][now.nc][i])) continue;
      if (dist[rr][cc]==-1)
      {
        dist[rr][cc]=dist[now.nr][now.nc]+1;
        Q.push(node(rr,cc));
      }
    }
  }
  printf("%d\n",ans);
  /*For(i,1,row)
  {
    For(j,1,col)
      printf("%3d ",dist[i][j]);
    pritnf("\n");
  }*/
#ifdef DEBUG  
  clock_t End_Time=clock();
  printf("\n\nTime Used: %.4lf Ms\n",double(End_Time-Start_Time)/CLOCKS_PER_SEC);
#endif    
  return 0;
}
//================fuction code====================