hdu 1076 nightmare

我会带着你远行 2022-08-23 11:57 60阅读 0赞

伊格修斯做了个噩梦，他们被困在一个迷宫中，迷宫中有炸弹，从他开始移动计时6mins后爆炸，他每分钟只能移动1格（上下左右），在迷宫中有炸弹重置装置，他到达那里可以将剩余时间设置为6mins，他能逃出去吗？炸弹重置装置可能没有也可能有多个。

题目思路：

初始思路是既然要找路那就先搜索最近的点是否有炸弹重置装置或终点，重点就结束输出最小值，炸弹重置装置就继续循环，没有就结束输出-1；感觉上还行，好像是正确的，但确实是错误的；要炸弹重置装置在6mins内都能达到，先找到了炸弹重置装置怎么办？？而且找到的最近的炸弹重置装置若不可能到达终点，而能走到较远的炸弹重置装置能走走到终点怎么办？？显然这个思路是错误的。。。。

错误代码如下：

#include<iostream>
    #include<cstdio>
    #include<queue>
    #include<cstring>
    #define N 10
    using namespace std;
    struct point
    {
    	int x,y,time;
    }S,E,q[105];
    int map[N][N],visit[N][N];
    int mov[4][2]={1,0,0,1,-1,0,0,-1};
    int n,m;
    int main()
    {
    	int T;
    	scanf("%d",&T);
    	while(T--)
    	{
    
    		point bfs();
    		scanf("%d%d",&n,&m);
    		for(int i=0;i<n;i++)
    		for(int j=0;j<m;j++)
    		{
    			scanf("%d",&map[i][j]);
    			if(map[i][j]==2){S.x=i;S.y=j;}
    			if(map[i][j]==3){E.x=i;E.y=j;}
    		}
    		int cou_time=0;
    		while(map[S.x][S.y]!=3)
    		{
    			memset(visit,0,sizeof(visit));
    			S=bfs();
    			if(S.time==-1)break;
    			cou_time+=6-S.time;
    			S.time=6;
    		}
    		if(S.time==-1)printf("-1\n");
    		else printf("%d\n",cou_time);
    	}
    	return 0;
    }
    point bfs()
    {
    	point cur,next;
    	q[0]=S;
    	q[0].time=6;
    	map[S.x][S.y]=0;
    	int fro=0,aft=1;
    	while(fro<aft)
    	{
    		cur=q[fro++];
    		for(int i=0;i<4;i++)
    		{
    			int tx,ty;
    			tx=cur.x+mov[i][0];
    			ty=cur.y+mov[i][1];
    			next.time=cur.time-1;
    			if(tx>=0&&tx<m&&ty>=0&&ty<m&&map[tx][ty]!=0&&!visit[tx][ty]&&next.time>0)
    			{
    				next.x=tx;next.y=ty;
    				if(map[tx][ty]==3||map[tx][ty]==4)return next;
    				q[aft++]=next;
    				visit[tx][ty]=1;
    			}
    		}
    	}
        next.time=-1;
        return  next;
    }

正确的思路是，走过的点用走过该点时的剩余时间来表示，当再遇到这个点时，判断当前剩余时间是否大于以前走过该点时的时间大于则可继续走，否则再走无意义

#include <iostream>
    using namespace std;
    #define inf 0x3fffffff
    #define M 10
    	//step[i][j]表示从起点到ij需要的最小步数，T[i][j]表示走到ij诈弹还剩下的时间
    int r, c, mins;
    int map[M][M], step[M][M], T[M][M];
    int x_move[4] = {-1, 0, 1, 0};
    int y_move[4] = {0, 1, 0, -1};
    
    void dfs (int x, int y)
    {
        if (T[x][y] <= 0)	//炸死了
            return ;
        if (map[x][y] == 3)
        {
            if (step[x][y] < mins)
                mins = step[x][y];
            return ;
        }
        for (int i = 0; i < 4; i++)
        {
            int tx = x + x_move[i];
            int ty = y + y_move[i];
            if (tx < 0 || tx >= r || ty < 0 || ty >= c)
                continue;
            if (map[tx][ty] == 0 ||
            step[tx][ty] <= step[x][y] + 1 && T[tx][ty] >= T[x][y] - 1)
                continue;    //已访问过，而且如果走下去诈弹时间没变甚至变小，那还不如不走呢
            step[tx][ty] = step[x][y] + 1;
            T[tx][ty] = T[x][y] - 1;
            if (map[tx][ty] == 4 && T[tx][ty] > 0)
                T[tx][ty] = 6;
            //将诈弹时间置为6，按照题意走到txty必须诈弹还有剩余时间，否则还是要爆
            dfs (tx, ty);
        }
    }
    
    int main()
    {
        int t, i, j, sx, sy;
        scanf ("%d", &t);
        while (t--)
        {
            scanf ("%d %d", &r, &c);
            for (i = 0; i < r; i++)
            {
                for (j = 0; j < c; j++)
                {
                    scanf ("%d", map[i]+j);
                    if (map[i][j] == 2)
                        sx = i, sy = j;
                    step[i][j] = inf;	//初始化步数为无穷大
                }
            }
            step[sx][sy] = 0;			//到起点的最小步数是0
            memset (T, 0, sizeof(T));	//初始化诈弹剩余时间为0
            T[sx][sy] = 6;				//起点的诈弹初始时间为6
            mins = inf;
            dfs (sx, sy);
            if (mins == inf)
                puts ("-1");
            else printf ("%d\n", mins);
        }
        return 0;
    }

广搜代码

#include<queue>
    #include<iostream>
    #include<stdio.h>
    using namespace std;
    struct ss
    {
        int x,y,step,t;
    };
    int map[100][100],mark[100][100],n,m,sx,sy;
    int r[4][2]={
       {1,0},{0,1},{-1,0},{0,-1}};
    void BFS()
    {
        queue<ss>Q;
        ss p,s;
        p.x=sx;
        p.y=sy;
        p.step=0;
        p.t=6;
        mark[p.x][p.y]=6;
        Q.push(p);
        int i;
        while (!Q.empty())
        {
            p=Q.front();
            Q.pop();
            for (i=0;i<4;i++)
            {
                s=p;
                s.x+=r[i][0];
                s.y+=r[i][1];
                if (s.x>=1&&s.x<=n&&s.y<=m&&s.y>=1&&map[s.x][s.y])
                {
                    s.t--;
                    s.step++;
                    if (map[s.x][s.y]==3)
                    {
                        printf("%d\n",s.step);
                        return ;
                    }
                    else if (map[s.x][s.y]==4)
                    {
                        s.t=6;
                        if (s.t>1&&mark[s.x][s.y]<s.t)
                        {
                            mark[s.x][s.y]=s.t;
                            Q.push(s);
                        }
                    }
                    else
                    {
                        if (s.t>1&&mark[s.x][s.y]<s.t)
                        {
                            mark[s.x][s.y]=s.t;
                            Q.push(s);
                        }
                    }
                }
            }
    
        }
        printf("-1\n");
    }
    int main()
    {
        int t,i,j;
        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;
                    }
                    mark[i][j]=0;
                }
            BFS();
        }
        return 0;
    }