hdoj搜索题集

n久没刷题了,感觉水平退化太多了。。今天开始刷题。
把hdoj以前没做的搜索题做一下
hdu1072 简单题
我的思路:出发点和可重置时间的点没有必要访问两次,其他点可以重复访问。这样不会导致bfs一直进行下去。
其他思路:对于这种点可以重复访问的题,bfs入队时不仅要考虑坐标,还要考虑剩余时间,如果同一个点第二次入队时剩余时间比第一次大于或等于,那么不需要入队,没有意义。

#include<stdio.h>
#include<string.h>
const int maxq=1000000;
int n,m;
int map[9][9];
int vis[9][9];
typedef struct Node{
    int x,y,t,step;
}Node;
Node q[maxq];
int iq;
int dirx[]={0,1,-1,0,0};
int diry[]={0,0,0,1,-1};
int sx,sy,tx,ty,x,y,tt,step;
bool judge(int x,int y)
{
    if(1<=x && x<=n && 1<=y && y<=m) return 1;
    return 0;
}
int bfs()
{
    int i,j;
    iq=0;memset(vis,0,sizeof(vis));
    q[iq].x=sx;q[iq].y=sy;q[iq].t=6;q[iq].step=0;
    iq++;vis[sx][sy]=1;
    for(i=0;i<=iq-1;i++)
    {
        x=q[i].x;y=q[i].y;tt=q[i].t;step=q[i].step;
        if(tt==1) continue;
        for(j=1;j<=4;j++)
        {
            int u=x+dirx[j],v=y+diry[j];
            if(map[u][v]==3) return step+1;
            if(!judge(u,v) || vis[u][v] || map[u][v]==0) continue;
            if(map[u][v]==4) vis[u][v]=1;
            q[iq].x=u;q[iq].y=v;q[iq].t=tt-1;q[iq].step=step+1;
            if(map[u][v]==4) q[iq].t=6;
            iq++;
        }
    }
    return -1;
}
int main()
{
    int i,j;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                scanf("%d",&map[i][j]);
                if(map[i][j]==2) sx=i,sy=j;
                if(map[i][j]==3) tx=i,ty=j;
            }
        printf("%d\n",bfs());
    }
    return 0;
}

hdu1026 简单题
如果答案是1 second,仍然输出1 seconds哦

#include<stdio.h>
#include<string.h>
const int maxq=100000+10;
int n,m;
char map[110][110];
bool vis[110][110];
typedef struct Node{
    int x,y,t,tt;
    int pre;
}Node;
Node q[maxq];
int iq;
int a[]={0,1,-1,0,0};
int b[]={0,0,0,1,-1};
bool judge(int x,int y)
{
    if(1<=x && x<=n && 1<=y && y<=m) return 1;
    return 0;
}
int bfs()
{
    int i,j;
    iq=0;memset(vis,0,sizeof(vis));
    q[iq].x=1;q[iq].y=1;q[iq].t=0;q[iq].pre=-1;
    iq++;
    vis[1][1]=1;
    for(i=0;i<=iq-1;i++)
    {
        int x=q[i].x,y=q[i].y,t=q[i].t,tt=q[i].tt;
        if(x==n && y==m)
        {
            if('1'<=map[n][m] && map[n][m]<='9')
            {
                if(!tt) return i;
            }
            else return i;
        }
        if('1'<=map[x][y] && map[x][y]<='9' && tt)
        {
            q[iq].x=x;q[iq].y=y;q[iq].t=t+1;q[iq].tt=tt-1;
            q[iq++].pre=i;
            continue;
        }
        for(j=1;j<=4;j++)
        {
            int u=x+a[j],v=y+b[j];
            if(!judge(u,v) || vis[u][v] || map[u][v]=='X') continue;
            q[iq].x=u;q[iq].y=v;q[iq].t=t+1;q[iq].tt=map[u][v]-'0';
            q[iq++].pre=i;
            vis[u][v]=1;
        }
    }
    return -1;
}
void dfs(int cur)
{
    int x=q[cur].x,y=q[cur].y,t=q[cur].t,pre=q[cur].pre;
    int px=q[pre].x,py=q[pre].y;
    if(px==1 && py==1)
    {
        printf("%ds:(%d,%d)->(%d,%d)\n",t,px-1,py-1,x-1,y-1);
        return;
    }
    dfs(pre);
    if(px==x && py==y) printf("%ds:FIGHT AT (%d,%d)\n",t,x-1,y-1);
    else printf("%ds:(%d,%d)->(%d,%d)\n",t,px-1,py-1,x-1,y-1);
    return;
}
int main()
{
    int i,j;
    while(~scanf("%d%d",&n,&m))
    {
        getchar();
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
                scanf("%c",&map[i][j]);
            getchar();
        }
        int ans=bfs();
        if(ans==-1) {printf("God please help our poor hero.\nFINISH\n");continue;}
        printf("It takes %d seconds to reach the target position, let me show you the way.\n",q[ans].t);
        dfs(ans);
        printf("FINISH\n");

    }

    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>