记录编号	121370	评测结果	AAAAAAAAAA
题目名称	[USACO Jan09] 激光电话	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	0.009 s
提交时间	2014-09-19 16:42:31	内存使用	0.51 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <set>
#include <list>
#include <iterator>
#include <ctime>
#include <queue>
#include <stack>
#include <vector>
#include <functional>
#include <deque>
#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;
  int face;
  node (int nr=0,int nc=0,int face=0):nr(nr),nc(nc),face(face){}
};
//================var declaration=========================
const int MAXN=110;
#define map maps
char map[MAXN][MAXN];
int f[MAXN][MAXN][4];
int row,col,er,ec;
int mvr[]={-1,0,1,0};
int mvc[]={0,1,0,-1};
queue <node> Q;
//================function declaration====================

//================main code===============================
using namespace std;
int main()
{
  string ProgrammeName="lphone";
  string FloderName="COGS";
  freopen((ProgrammeName+".in").c_str(),"r",stdin);
  freopen((ProgrammeName+".out").c_str(),"w",stdout);
#ifdef DEBUG
  clock_t Start_Time=clock();
  system(("copy C:\\Users\\abc\\Desktop\\HouJikan\\"+FloderName+"\\standard.cpp C:\\Users\\abc\\Desktop\\HouJikan\\"+FloderName+"\\submit.txt").c_str());
#endif
  scanf("%d%d",&col,&row);
  cin.ignore(10,10);
  For(i,0,row)
    cin.getline(map[i],1000);
  bool first=true;
  For(i,0,row)
    For(j,0,col)
      if (map[i][j]=='C'&&first)
        For(o,0,3)
        {  
          Q.push(node(i,j,o));
          f[i][j][o]=0;
          map[i][j]='.';
          first=false;
        }
      else if (map[i][j]=='C'&&!first)
      { 
         er=i,ec=j,map[i][j]='.';
         f[i][j][0]=f[i][j][1]=f[i][j][2]=f[i][j][3]=INF;
      }
      else
        For(o,0,3)
          f[i][j][o]=INF;
  int res=INF;
  while (!Q.empty())
  {
     node now=Q.front();Q.pop();
     int rr=now.nr,cc=now.nc;
     if (rr==er&&cc==ec)
     {
        res=min(f[rr][cc][now.face],res);
        continue;
     }
     if (f[rr][cc][now.face]>=res) continue;
     rr+=mvr[now.face];
     cc+=mvc[now.face];
     while (rr>=0&&rr<=row&&cc>=0&&cc<=col&&map[rr][cc]=='.')
     {
       if (f[rr][cc][now.face]>f[now.nr][now.nc][now.face])
       {
         f[rr][cc][now.face]=f[now.nr][now.nc][now.face];
         Q.push(node(rr,cc,now.face));
       }
       rr+=mvr[now.face];
       cc+=mvc[now.face];
     }
     For(i,0,3)
       if (f[now.nr][now.nc][i]>f[now.nr][now.nc][now.face]+1)
       {
         f[now.nr][now.nc][i]=f[now.nr][now.nc][now.face]+1;
         Q.push(node(now.nr,now.nc,i));
       }
  }
  printf("%d\n",res);
#ifdef DEBUG
  clock_t End_Time=clock();
  printf("\n\nTime Used :%.6lf Ms\n",double(Start_Time-End_Time)/(-CLOCKS_PER_SEC));
#endif
  return 0;
}
//================function code===========================