首页 > 搜索 > BFS搜索 > HDU 3345-War Chess-BFS-[解题报告]HOJ
2014
03-16

HDU 3345-War Chess-BFS-[解题报告]HOJ

War Chess

问题描述 :

War chess is hh’s favorite game:
In this game, there is an N * M battle map, and every player has his own Moving Val (MV). In each round, every player can move in four directions as long as he has enough MV. To simplify the problem, you are given your position and asked to output which grids you can arrive.
Kakuro Extension Extension
In the map:
‘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.

输入:

The first line of the inputs is T, which stands for the number of test cases you need to solve.
Then T cases follow:
Each test case starts with a line contains three numbers N,M and MV (2<= N , M <=100,0<=MV<= 65536) which indicate the size of the map and Y’s MV.Then a N*M two-dimensional array follows, which describe the whole map.

输出:

The first line of the inputs is T, which stands for the number of test cases you need to solve.
Then T cases follow:
Each test case starts with a line contains three numbers N,M and MV (2<= N , M <=100,0<=MV<= 65536) which indicate the size of the map and Y’s MV.Then a N*M two-dimensional array follows, which describe the whole map.

样例输入:

5
3 3 100
...
.E.
..Y

5 6 4
......
....PR
..E.PY
...ETT
....TT

2 2 100
.E
EY

5 5 2
.....
..P..
.PYP.
..P..
.....

3 3 1
.E.
EYE
...

样例输出:

...
.E*
.*Y

...***
..**P*
..E*PY
...E**
....T*

.E
EY

..*..
.*P*.
*PYP*
.*P*.
..*..

.E.
EYE
.*.

广搜,要剪枝,不然Memory Limit Exceeded

走过的位置再走的话必须比以前剩的MV更多才会有更优的解

#include<stdio.h>
#include<queue>
using namespace std;
char map[110][110];
int a[4][2]={1,0,0,1,-1,0,0,-1};
int cont[110][110];//记录到这步剩余的MV
int n,m;
struct op
{
    int x,y;
    int ant;
}cur,next;
int judge(int x,int y)
{
    if(x>=0 && x<n && y>=0 &&y<m &&map[x][y]!='E' &&map[x][y]!='#'&&map[x][y]!='Y')
        return 1;
    return 0;
}
int jdge(int x,int y)
{
    if(x>=0 && x<n &&y>=0 &&y<m &&map[x][y]=='E')
        return 1;
    return 0;
}
void bfs(int s,int d,int k)
{
    queue<op>Q;
    int i,X,Y,xx,yy,j;
    cur.x=s;cur.y=d;cur.ant=k;
    Q.push(cur);
    while(!Q.empty())
    {
        cur=Q.front();
        Q.pop();
        if(cur.ant<=0)continue;
        for(i=0;i<4;i++)
        {
            next.x=X=cur.x+a[i][0];
            next.y=Y=cur.y+a[i][1];
            if(judge(X,Y)==1)
            {
            
                if(map[X][Y]=='.'||map[X][Y]=='P')
                    next.ant=cur.ant-1;
                else if(map[X][Y]=='T')
                    next.ant=cur.ant-2;
                    
                else if(map[X][Y]=='R')
                    next.ant=cur.ant-3;
                if(next.ant>=0)
                {
                    for(j=0;j<4;j++)
                    {
                        xx=next.x+a[j][0];
                        yy=next.y+a[j][1];
                        if(jdge(xx,yy)==1)
                            next.ant=0;    
                    }
                    if(cont[next.x][next.y]<next.ant)//只有next的剩余MV大于原来剩余的MV时才走到这步
                    {
                        cont[next.x][next.y]=next.ant;
                        Q.push(next);
                       if(map[next.x][next.y]!='P')
                           map[next.x][next.y]='*';
                    }
                }
            }
        }
    }
}
int main()
{
    int i,j,t,x,y,k;
    scanf("%d",&t);
    while(t--)
    {
        memset(cont,-1,sizeof(cont));
        scanf("%d%d%d",&n,&m,&k);
        for(i=0;i<n;i++)
        {
            scanf("%s",map[i]);
            for(j=0;j<m;j++)
                if(map[i][j]=='Y')
                {x=i;y=j;}
        }
        cont[x][y]=k;
        bfs(x,y,k);
        for(i=0;i<n;i++)
            puts(map[i]);
        printf("\n");
    }
    return 0;
}

参考:http://blog.csdn.net/aixiaoling1314/article/details/8797899


,
  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-1])这个地方也也有笔误
    应改为L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-2])