hdu 1026 宽搜+标记路径

约定不等于承诺〃 2022-08-08 14:50 20阅读 0赞

题意：

给定一个起点和终点，还有一个图，在图上"."的点，可以花1s的时间走完，如果该点上是一个数，则需要花该数的时间，在该点打败怪兽，给出从起点到终点的所需要的最短的时间。具体输出描述请看题目hdu 1026。

解题思路：

典型的宽搜题，稍微麻烦点的是，需要在宽搜的时候记录路径，我是采用了记录上一步是从哪个点来的方式。也可以用数组记录下每条线路的整个路径，不过需要很大的空间，还需要一些代码上的优化，我觉得还是记录父亲节点的方式时间和空间的效率更高。

至于具体的搜索方法，可以在网上搜到很多具体的教程，我就不献丑了，肯定讲的没那些教案全。我的理解是，每次拓展一层节点，比如一开始只能在（0,0）点，有4个方向可以走，将确实可以走的点，记录下来，加入宽搜的数组。这样在这层就有了0~4个可以拓展的点，每个点扩展一遍，就可能有0~16个点，这样循环下去。最终搜出了所有到达终点的路径，加一些剪枝判断就可以大量减少需要添加的点。这是非常显著的，比如你在第一层少加了一个没有价值的点，以后如果有10层，就少了4^10次的操作和更多的空间。这样的优化方法有很多，但是因为这题需要把所有路径搜出来作为比较，不能采用一些方向上的贪心优化，因为不可以一找到结果就退出。

如果大家有问题，欢迎提问。

代码：

#include <iostream>
    #include <cstring>
    #include <string.h>
    using namespace std;
    
    int dx[4],dy[4],i,j,k,n,m,ansPoint,minTime,l,r;
    int mapp[100][100];
    char c;
    int mapTime[100][100];
    
    struct {
        int x;
        int y;
        int parent;
        int stime;
    }way[1000000];
    
    void Dfs(int k) {
        if (way[k].parent != -1) Dfs(way[k].parent);
        int i;
        if (way[k].parent != -1) {
                cout << way[k].stime - mapp[way[k].x][way[k].y] << "s:" << '(' << way[way[k].parent].x << ',' << way[way[k].parent].y << ")->(" << way[k].x << ',' << way[k].y << ')' << endl;
                for (i = way[k].stime - mapp[way[k].x][way[k].y]; i < way[k].stime; i++) {
                    cout << i+1 << "s:" << "FIGHT AT " << '(' << way[k].x << ',' << way[k].y << ')' << endl;
                }
        }
    }
    
    int main(){
        dx[0] = 0; dx[1] = 1; dx[2] = 0; dx[3] = -1;
        dy[0] = 1; dy[1] = 0; dy[2] = -1; dy[3] = 0;
    
        //Input
        while (cin >> n >> m) {
            for (i = 0; i < n; i++)
                for (j = 0; j < m; j++) {
                    cin >> c;
                    if (c == '.') {
                        mapp[i][j] = 0;
                    } else
                    if (c == 'X') {
                        mapp[i][j] = -1;
                    } else {
                        mapp[i][j] = c - '0';
                    }
                }
    
        //BFS
        minTime = 100000000;
        l = 0;
        r = 0;
        way[0].x = 0;
        way[0].y = 0;
        way[0].parent = -1;
        way[0].stime = 0;
        memset(mapTime, 0x7F, sizeof(mapTime)) ;
        mapTime[0][0] = 0;
        while (l <= r) {
            k = r;
            for (i = l; i <= r; i++) {
                for (j = 0; j <= 3; j++)
                    if (mapp[way[i].x+dx[j]][way[i].y+dy[j]] != -1&&way[i].x+dx[j]>=0&&way[i].y+dy[j]>=0&&way[i].x+dx[j]<n&&way[i].y+dy[j]<m)
                       if (way[i].stime + mapp[way[i].x+dx[j]][way[i].y+dy[j]] + 1 < mapTime[way[i].x+dx[j]][way[i].y+dy[j]]) {
                        k++;
                        way[k].x = way[i].x+dx[j];
                        way[k].y = way[i].y+dy[j];
                        mapTime[way[k].x][way[k].y] = way[i].stime + mapp[way[k].x][way[k].y] + 1;
                        way[k].parent = i;
                        way[k].stime = way[i].stime + mapp[way[k].x][way[k].y] + 1;
                        if ((way[k].x == n - 1) &&(way[k].y == m - 1))
                            if (way[k].stime < minTime) {
                                minTime = way[k].stime;
                                ansPoint = k;
                        }
                    }
            }
            l = r + 1;
            r = k;
        }
    
        //Out
        if (minTime == 100000000) {
            cout << "God please help our poor hero." << endl;
            cout << "FINISH" << endl;
        } else {
            cout << "It takes " << minTime << " seconds to reach the target position, let me show you the way." << endl;
            Dfs(ansPoint);
            cout << "FINISH" << endl;
        }
        }
        return 0;
    }