记录编号	118516	评测结果	AAAAA
题目名称	[CTSC 1999] 拯救大兵瑞恩	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	0.048 s
提交时间	2014-09-07 11:33:14	内存使用	0.32 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=0x7fffffff;
//==============struct declaration==============
struct node
{
  Uint nr,nc,key,dist;
  int pa;
  node (Uint nr=0,Uint nc=0,Uint key=0,Uint dist=0,int pa=-1):nr(nr),nc(nc),key(key),dist(dist),pa(pa){}
} ;
//==============var declaration=================
int mvr[]={-1,0,1,0};//上右下左 
int mvc[]={0,1,0,-1};//上右下左
//以左上角为(1,1) 
Uint block[20][20][5]; 
Uint key[20][20];
int keyn;
int r,c,p,k;//p是钥匙种数,k是墙个数 
//==============function declaration============
void adddoor(int r1,int c1,int r2,int c2,int kind);
bool moveable (node now,int x);
//==============main code=======================
int main()
{  
  string FileName="rescue";//程序名 
  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%d%d",&r,&c,&p,&k);
  memset(block,0,sizeof(block));
  memset(key,0,sizeof(key));
  int r1,r2,c1,c2,kind;
  For(i,1,k)
  {
    scanf("%d%d%d%d%d",&r1,&c1,&r2,&c2,&kind);
    adddoor(r1,c1,r2,c2,kind);
  }
  scanf("%d",&keyn);
  For(i,1,keyn)
  {
    scanf("%d%d%d",&r1,&c1,&kind);
    key[r1][c1]|=(1<<kind);
  }
  queue <node> Q;
  Q.push(node(1,1,0,0));
  while (!Q.empty())
  {
     node now=Q.front();Q.pop();
     if (now.nr==r&&now.nc==c)
     {
       printf("%d\n",now.dist);
       return 0;
     }
     if ((now.key|key[now.nr][now.nc])!=now.key)
     {
       now.key|=key[now.nr][now.nc];
       now.pa=-1;
     }
     For(pos,0,3)
     {
       if (pos==now.pa) continue;
       if (moveable(now,pos))
         Q.push(node(now.nr+mvr[pos],now.nc+mvc[pos],now.key,now.dist+1,(pos+2)%4));
     }
  }
  pritnf("-1\n");
#ifdef DEBUG  
  clock_t End_Time=clock();
  cout<<endl<<endl<<"Time Used: "<<(End_Time-Start_Time)/CLOCKS_PER_SEC<<endl;
#endif    
  return 0;
}
//================fuction code====================
void adddoor(int r1,int c1,int r2,int c2,int kind)
{
  For(i,0,3)
  {
    if (r1+mvr[i]==r2&&c1+mvc[i]==c2)
      block[r1][c1][i]|=(1<<kind);
    if (r2+mvr[i]==r1&&c2+mvc[i]==c1)
      block[r2][c2][i]|=(1<<kind);
  }
}
bool moveable (node now,int x)
{
  if (now.nr+mvr[x]>=1&&now.nr+mvr[x]<=r&&now.nc+mvc[x]<=c&&now.nc+mvc[x]>=1)
  {
    int b=block[now.nr][now.nc][x];
    int keys=now.key;
    For(i,0,p)
      if (b&(1<<i))
        if (!(keys&(1<<i)))
          return false;
    return true;
  }
  return false;
}