题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=4528
方法：地图输入接收完成后，扫面数组，把所有可以看到D和E的位置都标记了，d表示可以看到D，e表示可以看到E,b表示两个都可以看到，这一步放在广搜前的初始化里面。在广搜时，树中的每一个状态节点有3个信息，图中坐标x y，到当前有没有已经看到D getD，到当前有没有已经看到E getE,和当前使用的时间。探寻到一个状态节点，将不将其放入优先队列，从不从该节点开始广搜判断的依据为改状态所处位子是不是墙或D或E（题目要求不能穿过D或E）已经该状态有没有搜索过。判断一个状态有没有搜索过，主要由一个4维变量来记录其访问情况，即用v[x][y][getD][getE]来表示。
除此之外，由于题目要求有时间限制，所以可以用当前使用的时间来剪枝。
感想：重点在于模拟。
代码：
View Code
#include <iostream> #include <queue> using namespace std; int n,m,timeLimit; int Dx,Dy,Ex,Ey,Sx,Sy; char map[102][102]; bool v[102][102][2][2]; char start = 'S'; char D ='D'; char E ='E'; char canGetD = 'd'; char canGetE = 'e'; char canGetBoth='b'; char wall = 'X'; char road = '.'; int deriction[4][2]={{0,1},{1,0},{0,-1},{-1,0}}; struct Location { int x,y; int time; bool getD; bool getE; }; struct cmp { bool operator()(Location x,Location y) { if(x.time>y.time) return true; return false; } }; bool canGo(int x,int y,bool canGetD,bool canGetE) { return map[x][y]!=wall && map[x][y]!=D && map[x][y]!=E && !v[x][y][canGetD][canGetE]; } void initialize() { int t_x=Dx,t_y=Dy; while(map[t_x+1][t_y]!=wall && map[t_x+1][t_y]!=E) { if(map[t_x+1][t_y]==road || map[t_x+1][t_y]==start) map[t_x+1][t_y] =canGetD; else map[t_x+1][t_y] = canGetBoth; t_x++; } t_x=Dx,t_y=Dy; while(map[t_x-1][t_y]!=wall && map[t_x-1][t_y]!=E) { if(map[t_x-1][t_y]==road || map[t_x-1][t_y]==start) map[t_x-1][t_y] = canGetD; else map[t_x-1][t_y] = canGetBoth; t_x--; } t_x=Dx,t_y=Dy; while(map[t_x][t_y+1]!=wall && map[t_x][t_y+1]!=E) { if(map[t_x][t_y+1]==road || map[t_x][t_y+1]==start) map[t_x][t_y+1] = canGetD; else map[t_x][t_y+1] = canGetBoth; t_y++; } t_x=Dx,t_y=Dy; while(map[t_x][t_y-1]!=wall && map[t_x][t_y-1]!=E) { if(map[t_x][t_y-1]==road || map[t_x][t_y-1]==start) map[t_x][t_y-1] = canGetD; else map[t_x][t_y-1] = canGetBoth; t_y--; } t_x=Ex,t_y=Ey; while(map[t_x+1][t_y]!=wall && map[t_x+1][t_y]!=D) { if(map[t_x+1][t_y]==road || map[t_x+1][t_y]==start) map[t_x+1][t_y] = canGetE; else map[t_x+1][t_y] = canGetBoth; t_x++; } t_x=Ex,t_y=Ey; while(map[t_x-1][t_y]!=wall &&map[t_x-1][t_y]!=D ) { if(map[t_x-1][t_y]==road || map[t_x-1][t_y]==start) map[t_x-1][t_y] = canGetE; else map[t_x-1][t_y] = canGetBoth; t_x--; } t_x=Ex,t_y=Ey; while(map[t_x][t_y+1]!=wall &&map[t_x][t_y+1]!=D ) { if(map[t_x][t_y+1]==road || map[t_x][t_y+1]==start) map[t_x][t_y+1] = canGetE; else map[t_x][t_y+1] = canGetBoth; t_y++; } t_x=Ex,t_y=Ey; while(map[t_x][t_y-1]!=wall && map[t_x][t_y-1]!=D ) { if(map[t_x][t_y-1]==road || map[t_x][t_y-1]==start) map[t_x][t_y-1] = canGetE; else map[t_x][t_y-1] = canGetBoth; t_y--; } } int BFSearch() { initialize(); Location startLocation; startLocation.x = Sx; startLocation.y = Sy; startLocation.time = 0; startLocation.getD = map[startLocation.x][startLocation.y] ==canGetD ||map[startLocation.x][startLocation.y] == canGetBoth; startLocation.getE = map[startLocation.x][startLocation.y] ==canGetE ||map[startLocation.x][startLocation.y] == canGetBoth; priority_queue<Location,vector<Location>,cmp> q; q.push(startLocation); while(!q.empty()) { Location t_location = q.top(); q.pop(); if(t_location.getD && t_location.getE) return t_location.time; else { if(!v[t_location.x][t_location.y][t_location.getD][t_location.getE]) { v[t_location.x][t_location.y][t_location.getD][t_location.getE]= true; int n_x,n_y; bool n_getD,n_getE; Location n_location; for(int i=0;i<4;i++) { n_x = t_location.x + deriction[i][0]; n_y = t_location.y + deriction[i][1]; n_getD = map[n_x][n_y] ==canGetD || t_location.getD|| map[n_x][n_y] == canGetBoth; n_getE = map[n_x][n_y] ==canGetE || t_location.getE|| map[n_x][n_y] == canGetBoth; if(canGo(n_x,n_y,n_getD,n_getE) && t_location.time+1<=timeLimit) { n_location.x = n_x; n_location.y = n_y; n_location.time = t_location.time+1; n_location.getD = n_getD; n_location.getE =n_getE; q.push(n_location); } } } } } return -1; } void main() { int tc=0,t; scanf("%d",&t); while(tc<t) { memset(map,'X',sizeof(map)); memset(v,false,sizeof(v)); scanf("%*c %d %d %d",&n,&m,&timeLimit); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { cin>>map[i][j]; if(map[i][j] ==D) { Dx = i; Dy = j; } if(map[i][j] == E) { Ex = i; Ey = j; } if(map[i][j] ==start) { Sx = i; Sy = j; } } cout<<"Case "<<tc+1<<":"<<endl<<BFSearch()<<endl; tc++; } }