hdu5040 （2014北京网赛1009） Instrusive

本文主要是介绍hdu5040 （2014北京网赛1009） Instrusive，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

        题意：n*n网格走迷宫。。迷宫中有障碍物不能走过去。迷宫中还有一些相机，人不能被相机照到。每个相机有朝向，照的距离是2（相机本身格子和朝向的下一个格子），每秒所有相机顺时针转90度。人走到相邻格子花1秒，并且有一个隐身技能，可以隐着身不走，如果要隐身走，则花3秒。具体规则是：如果当前格子被照到，必须隐身，如果将要走到的格子被照到，也必须隐身走过去。

        思路：状态空间搜索。开三维状态，一、二维是行、列，第三维是时间模4，因为相机的状态只有4种。无论什么情况，总是可以隐身走动或者隐身不走的。但是如果需要不隐身走，就需要进行稍微复杂的判断，我是开了10个bool变量。。。具体见代码。

#include <iostream>    
#include <stdio.h>    
#include <cmath>    
#include <algorithm>    
#include <iomanip>    
#include <cstdlib>    
#include <string>    
#include <memory.h>    
#include <vector>    
#include <queue>    
#include <stack>    
#include <map>  
#include <set>  
#include <ctype.h>    using namespace std;  char mp[510][510];
int dirn[]={-1,0,1,0};
int dirm[]={0,1,0,-1};int a[510][510][4];struct node{int n;int m;int dis;node(int a,int b,int c){n=a; m=b; dis=c;}bool operator<(node nb)const{return dis>nb.dis;}
};int main(){int t;cin>>t;int cas=0;while(t--){cas++;memset(a,-1,sizeof(a));int n;cin>>n;int startn,startm;int endn,endm;for(int i=1;i<=n;i++){scanf("%s",mp[i]+1);for(int j=1;j<=n;j++){if(mp[i][j]=='M'){startn=i; startm=j;}else if(mp[i][j]=='T'){endn=i; endm=j;}else if(mp[i][j]=='N'){mp[i][j]=0;}else if(mp[i][j]=='E'){mp[i][j]=1;}else if(mp[i][j]=='S'){mp[i][j]=2;}else if(mp[i][j]=='W'){mp[i][j]=3;}}}int ans=0;node start(startn,startm,1); a[startn][startm][1]=1;priority_queue<node> que; que.push(start);while(!que.empty()){node cur=que.top(); que.pop();int cn=cur.n;int cm=cur.m;int cdis=cur.dis;if(cn==endn&&cm==endm){ans=cdis;break;}for(int i=0;i<4;i++){int newn=cn+dirn[i];int newm=cm+dirm[i];if(newn>n||newn<1||newm>n||newm<1)continue;if(mp[newn][newm]=='#')continue;int statu=(cdis+3)%4;if(a[newn][newm][statu]==-1||cdis+3<a[newn][newm][statu]){a[newn][newm][statu]=cdis+3;node nd(newn,newm,cdis+3);que.push(nd);}//符合以下条件其中一种就不能花1秒来移动了，简直。。。 bool cs0=newn<n&& mp[newn+1][newm]<4 && ((mp[newn+1][newm]+cdis)%4)==1; //N相机 bool cs1=newm>1&& mp[newn][newm-1]<4 && ((mp[newn][newm-1]+cdis)%4)==2; //E相机bool cs2=newn>1&& mp[newn-1][newm]<4 && ((mp[newn-1][newm]+cdis)%4)==3; //S相机bool cs3=newm<n&& mp[newn][newm+1]<4 && ((mp[newn][newm+1]+cdis)%4)==0; //W相机bool cs4=cn<n&& mp[cn+1][cm]<4 && ((mp[cn+1][cm]+cdis)%4)==1; //N相机 bool cs5=cm>1&& mp[cn][cm-1]<4 && ((mp[cn][cm-1]+cdis)%4)==2; //E相机bool cs6=cn>1&& mp[cn-1][cm]<4 && ((mp[cn-1][cm]+cdis)%4)==3; //S相机bool cs7=cm<n&& mp[cn][cm+1]<4 && ((mp[cn][cm+1]+cdis)%4)==0; //W相机bool cs8=mp[newn][newm]>=0&&mp[newn][newm]<=3;  //走到相机上 bool cs9=mp[cn][cm]>=0&&mp[cn][cm]<=3;  //当前在相机上 if(cs0||cs1||cs2||cs3||cs4||cs5||cs6||cs7||cs8||cs9)continue;statu=(cdis+1)%4;if(a[newn][newm][statu]==-1||cdis+1<a[newn][newm][statu]){a[newn][newm][statu]=cdis+1;node nd(newn,newm,cdis+1);que.push(nd);}}if(a[cn][cm][(cdis+1)%4]==-1||cdis+1<a[cn][cm][(cdis+1)%4]){a[cn][cm][(cdis+1)%4]=cdis+1;node nd(cn,cm,cdis+1);que.push(nd);}}printf("Case #%d: %d\n",cas,ans-1);}return 0;
}

这篇关于hdu5040 （2014北京网赛1009） Instrusive的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---