hdu 3345 （BFS）

刚开始没用二维数组存每次更新出来的最大的mv值，后来看阶梯报告才发现可以这样做啊。。。。

需要注意一下，
当你遇到E时，只有当v值>0时，才让v=0；
即v=0时,v=0;
否则不用；
这里有点坑

2013/04/22-13:25

[cpp]
#include"stdio.h"
#include"string.h"
#include"queue"
#define N 111
using namespace std;

char map[N][N],ans[N][N];
//map--原始串，ans---更新的串
int dir[4][2]={1,0,0,1,-1,0,0,-1};
int n,m,mv;
int X,Y;
int dp[N][N];
//dp[x][y]--存x,y位置的最大mv值
struct node
{
    int x,y,v;
}p,q;

queue<node>Q;
//判断函数
int judge(int x,int y)
{
    if(x>=0&&x<n&&y>=0&&y<m)return 1;
    return 0;
}
//对v处理
int fun(int x,int y,int v)
{
    int i;
    int xx,yy,vv;
    if(map[x][y]=='T')vv=v-2;
    else if(map[x][y]=='R')vv=v-3;
    else vv=v-1;
    for(i=0;i<4;i++)
    {
        xx=x+dir[i][0];
        yy=y+dir[i][1];
        if(judge(xx,yy)&&map[xx][yy]=='E')
            /*这里需要注意一下，
            当你遇到E时，只有当v值>0时，才让v=0；
            即v=0时,v=0;
            否则不用；
            这里有点坑
              */
            return vv>0?0:vv;
    }
    return vv;
}
void bfs()
{
    int i;
    p.x=X;
    p.y=Y;
    p.v=mv;
    Q.push(p);
    dp[X][Y]=mv;
    ans[X][Y]='Y';
    while(!Q.empty())
    {
        p=Q.front();
        Q.pop();
        if(p.v==0)continue;
        for(i=0;i<4;i++)
        {
            q.x=p.x+dir[i][0];
            q.y=p.y+dir[i][1];
            q.v=p.v;
            if(!judge(q.x,q.y))continue;
            if(map[q.x][q.y]=='Y'
                ||map[q.x][q.y]=='E'||map[q.x][q.y]=='#')continue;
            q.v=fun(q.x,q.y,q.v);
            if(q.v<0)continue;
            if(q.v>dp[q.x][q.y])
            {
                dp[q.x][q.y]=q.v;
                Q.push(q);
                if(map[q.x][q.y]!='P')
                    ans[q.x][q.y]='*';
            }
        }
    }
}


int main()
{
    int T,i,j;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&n,&m,&mv);
        getchar();
        memset(dp,-1,sizeof(dp));
        for(i=0;i<n;i++)
        {
            gets(map[i]);
            for(j=0;map[i][j];j++)
            {
                if(map[i][j]=='Y')
                {
                    X=i;Y=j;
                }
                ans[i][j]=map[i][j];
            }
            ans[i][m]='\0';
        }
        bfs();
        for(i=0;i<n;i++)
            puts(ans[i]);
        printf("\n");
    }
    return 0;
}

#include"stdio.h"
#include"string.h"
#include"queue"
#define N 111
using namespace std;

char map[N][N],ans[N][N];
//map--原始串，ans---更新的串
int dir[4][2]={1,0,0,1,-1,0,0,-1};
int n,m,mv;
int X,Y;
int dp[N][N];
//dp[x][y]--存x,y位置的最大mv值
struct node
{
int x,y,v;
}p,q;

queue<node>Q;
//判断函数
int judge(int x,int y)
{
if(x>=0&&x<n&&y>=0&&y<m)return 1;
return 0;
}
//对v处理
int fun(int x,i

补充：软件开发 , C++ ,