HDU 3345 War Chess BFS - c++编程基础

N*M的图。
'Y' is your current position (there is one and only one Y in the given map).
'.' is a normal grid. It costs you 1 MV to enter in this gird.
'T' is a tree. It costs you 2 MV to enter in this gird.
'R' is a river. It costs you 3 MV to enter in this gird.
'#' is an obstacle. You can never enter in this gird.
'E's are your enemies. You cannot move across your enemy, because once you enter the grids which are adjacent with 'E', you will lose all your MV. Here “adjacent” means two grids share a common edge.
'P's are your partners. You can move across your partner, but you cannot stay in the same grid with him final, because there can only be one person in one grid.You can assume the Ps must stand on '.' . so ,it also costs you 1 MV to enter this grid.
给出一张图，和总共的步数。
然后输出走过的图，能走的地方都用*标记。
A了10来个小时，第一次用DFS做，标记visit[][],然后回溯，但是直接TLE。因为visit[][]标记的只是一次步数全部走完路径，走完之后就都回溯了，这样就造成很多重复的步骤。
第二次换了BFS，但是没有用标记数组，直接爆栈了T_T。
第三次还是BFS，但是加了个visit[][]数组来储存步数，在搜索的过程中，每次走到这一步，都更新visit[][]的步数，使得走到坐标（x,y）的剩余步数最大。
[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define PI acos(-1.0)
#define Max 2005
#define inf 1<<28
using namespace std;

char Map1[Max][Max];//原图
char Map2[Max][Max];//输出的图
int visit[Max][Max];//储存步数
int n,m;
int movex[4]= {1,-1,0,0};
int movey[4]= {0,0,1,-1};
struct kdq
{
int x,y,num;
};
int inmap(int x,int y)//判断该点是否可以到达
{
if(x<=0||y<=0||x>n||y>m||Map1[x][y]=='#'||Map1[x][y]=='E'||Map1[x][y]=='Y')
return 0;
return 1;
}
int isEnemies(int x,int y)//判断四个方向是否有E存在，有的话就停止。
{
int i,j;
for(i=0; i<4; i++)
{
int tx=x+movex[i];
int ty=y+movey[i];
if(inmap(tx,ty)&&Map1[tx][ty]=='E')
return 1;
}
return 0;
}
int movesum(int x,int y,int move)//计算走到这一步的步数，返回剩余步数。

{
int movenum,i;
if(Map1[x][y]=='T')
movenum=move-2;
if(Map1[x][y]=='R')
movenum=move-3;
if(Map1[x][y]=='.')
movenum=move-1;
if(Map1[x][y]=='P')
movenum=move-1;
for(i=0; i<4; i++)//判断走到这一步后，四个方向上是否有E存在，有的话直接break;
{
int tx=x+movex[i];
int ty=y+movey[i];
if(tx>0&&ty>0&&tx<=n&&ty<=m&&Map1[tx][ty]=='E')
break;
}
if(i!=4)//i!=4,即是 break出来的，那么证明这一点四个方向上有E存在，那么则无法移动，即剩余步数为0。
{
if(movenum>0)
movenum=0;
}
return movenum;//返回步数
}
void bfs(int x,int y,int move)
{
kdq a;
int i,j;
for(i=0;i<=n;i++)//初始化visit[][]为无穷小
for(j=0;j<=m;j++)
visit[i][j]=-inf;
a.x=x;
a.y=y;
a.num=move;
queueq;
q.push(a);
visit[x][y]=move;//初始的步数
int num=0;
while(!q.empty())
{
kdq temp=q.front();
q.pop();
if(temp.num==0)//如果步数为0，则不需要继续下去，直接continue;
continue;
if(num)if(isEnemies(temp.x,temp.y))continue;//因为如果初始位置四个方向上有E的话，Y是可以移动的，所以用一个num来表示这一步是不是移动的第一步。
//如果不是第一步，并且四个方向上有E，则无法移动。continue;
num++;//标记是否是第一步的移动
for(int i=0;i<4;i++)
{
int tx=temp.x+movex[i];
int ty=temp.y+movey[i];
if(inmap(tx,ty))
{
kdq now;
now.num=movesum(tx,ty,temp.num);//计算剩余步骤
//if(Map1[tx][ty]=='P'&&now.num<1)continue;
if(now.num<0)continue;
if(now.num>visit[tx][ty])//更新visit[][]

HDU 3345 War Chess BFS(一)