列表

详情

LCP 21. 追逐游戏

秋游中的小力和小扣设计了一个追逐游戏。他们选了秋日市集景区中的 N 个景点，景点编号为 1~N。此外，他们还选择了 N 条小路，满足任意两个景点之间都可以通过小路互相到达，且不存在两条连接景点相同的小路。整个游戏场景可视作一个无向连通图，记作二维数组 edges，数组中以 [a,b] 形式表示景点 a 与景点 b 之间有一条小路连通。

小力和小扣只能沿景点间的小路移动。小力的目标是在最快时间内追到小扣，小扣的目标是尽可能延后被小力追到的时间。游戏开始前，两人分别站在两个不同的景点 startA 和 startB。每一回合，小力先行动，小扣观察到小力的行动后再行动。小力和小扣在每回合可选择以下行动之一：

如果小力追到小扣（即两人于某一时刻出现在同一位置），则游戏结束。若小力可以追到小扣，请返回最少需要多少回合；若小力无法追到小扣，请返回 -1。

注意：小力和小扣一定会采取最优移动策略。

示例 1：

输入：edges = [[1,2],[2,3],[3,4],[4,1],[2,5],[5,6]], startA = 3, startB = 5

输出：3

解释： image.png{:height="250px"}

第一回合，小力移动至 2 号点，小扣观察到小力的行动后移动至 6 号点； 第二回合，小力移动至 5 号点，小扣无法移动，留在原地； 第三回合，小力移动至 6 号点，小力追到小扣。返回 3。

示例 2：

输入：edges = [[1,2],[2,3],[3,4],[4,1]], startA = 1, startB = 3

输出：-1

解释： image.png{:height="250px"}

小力如果不动，则小扣也不动；否则小扣移动到小力的对角线位置。这样小力无法追到小扣。

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: int chaseGame(vector<vector<int>>& edges, int startA, int startB) { } };

java 解法, 执行用时: 43 ms, 内存消耗: 92.7 MB, 提交时间: 2023-10-27 22:32:57 

class Solution {
      public int chaseGame(int[][] edges, int startA, int startB) {
        //n个顶点n条边
        int n = edges.length;
        List<List<Integer>> list = new ArrayList<>(n+1);
        //初始化一下
        for (int i = 0; i <= n; i++) {
            list.add(new ArrayList<>());
        }
        //记录顶点的数量
        int[] nums = new int[n+1];
        for(int[] arr : edges){
            //无向图
            list.get(arr[0]).add(arr[1]);
            list.get(arr[1]).add(arr[0]);
            nums[arr[0]]++;
            nums[arr[1]]++;
        }
        //标记到起点的距离
        int[] distA = new int[n + 1];
        int[] distB = new int[n + 1];
        bfs(list, distA, startA);
        bfs(list, distB, startB);
        //找出环
        int ring = n;
        Queue<Integer> queue = new LinkedList<>();
        //添加叶子节点
        for (int i = 1; i <= n; i++) if(nums[i]==1) queue.add(i);
        while (!queue.isEmpty()){
            Integer f = queue.poll();
            ring--;
            for(Integer v : list.get(f)){
                nums[v]--;
                if(nums[v] == 1) queue.add(v);
            }
        }
        //追上的步骤
        int ans = 1;
        for (int i = 1; i <= n; i++) {
            if(distA[i] > distB[i] + 1){
                //表示这是环上的点，B可以先一步到达
                if(nums[i] > 1 && ring > 3){
                    ans = -1;
                    break;
                }else{
                    ans = Math.max(ans,distA[i]);
                }
            }
        }
        return ans;
    }

    private void bfs(List<List<Integer>> list,int[] dist,int x){
        Queue<Integer> queue = new LinkedList<>();
        //起点
        queue.add(x);
        //先初始化为-1
        dist[x] = 0;
        while (!queue.isEmpty()){
            Integer f = queue.poll();
            for(Integer v : list.get(f)){
                if(dist[v] == 0 && v!=x){
                    dist[v] = dist[f] + 1;
                    queue.add(v);
                }
            }
        }
    }
}

java 解法, 执行用时: 97 ms, 内存消耗: 126 MB, 提交时间: 2023-10-27 22:32:30 

class Solution {
//邻接表图
    Set<Integer>[] graph;
    //储存环节点集合
    Set<Integer> hoops;
    //边数据集
    int[][] edges;
    //环入口点
    int firstHoop;
    public int chaseGame(int[][] edges, int startA, int startB) {
        this.edges=edges;
        //建图
        createGraph(edges);
        //第一种情况：A和B直接相连则直接返回1
        if(graph[startA].contains(startB)) return 1;
        //储存环内节点
        hoops=new HashSet<>();
        //记录每个点的父节点
        int[] parent=new int[edges.length+1];
        //dfs找环
        dfs(parent,-1,1,new boolean[edges.length+1]);
        int temp=firstHoop;
        hoops.add(temp);
        //遍历父节点数组，结束条件为该点的父节点是环入口
        while (parent[temp]!=firstHoop){
            temp=parent[temp];
            hoops.add(temp);//将环加入集合
        }
        //得到A和B的距离数组
        int[] valA=getDist(startA,new boolean[edges.length+1]);
        int[] valB=getDist(startB,new boolean[edges.length+1]);
        //得到B进入环的最小距离的点
        int interInd = getInterInd(valB);
        //第二种情况：环的节点大于3并且B可以到达环，则A永远追不上B
        if(hoops.size()>3&&valA[interInd]-1>valB[interInd]) return -1;
        //第三种情况A一定可以追上B
        return maxVal(valA, valB,startB,new boolean[edges.length+1]);

    }
    boolean finished=false;
    /**
     * dfs找环
     * @param parent 父节点数组
     * @param pa 上一个已经访问的点
     * @param ch 当前访问的点
     * @param visited 标记数组
     */
    public void dfs(int[] parent,int pa,int ch,boolean[] visited){
        //判断是否找到环入口点
        if(visited[ch]){
            finished=true;//标记
            firstHoop=ch;//记录环入口
            return;
        }
        visited[ch]=true;
        Set<Integer> set = graph[ch];
        for (Integer i : set) {
            if(!finished&&i!=pa){
                parent[i]=ch;
                dfs(parent,ch,i,visited);
            }
        }
    }

    /**
     * 递归遍历B可以到达的点
     * @param valA A与每个点的距离
     * @param valB B与每个点的距离
     * @param i 可以到达的点
     * @param visited 标记数组
     * @return B与A最远的距离
     */
    public int maxVal(int[] valA,int[]valB,int i,boolean[] visited){
        visited[i]=true;
        Set<Integer> set = graph[i];
        int max=valA[i];
        for (Integer c : set) {
            /**
             * B能够到达点c的条件为：B与c的距离严格大于A与c距离-1
             * valA[ch]-1>valB[ch]
             */
            if(!visited[c]&&valA[c]-1>valB[c]){
                max=Math.max(max,maxVal(valA,valB,c,visited));
            }
        }
        return max;
    }

    /**
     * 求出A或B进入环，花费距离最小的入口点
     * @param val 各个点到A或B的距离数组
     * @return 环入口点坐标
     */
    public int getInterInd(int[] val){
        int minB=1000000;
        int index=-1;
        //遍历环集合
        for (Integer i : hoops) {
            if(val[i]<minB){
                minB=val[i];
                index=i;
            }
        }
        return index;
    }

    /**
     * bfs求出每个点到点start的距离
     * @param start 目标点
     * @return 返回距离数组
     */
    public int[] getDist(int start,boolean[] visited){
        int[] valStart=new int[edges.length+1];
        int v=0;//点到start的距离
        visited[start]=true;
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(start);
        while (!queue.isEmpty()){
            int size = queue.size();
            //得到当前层的节点
            for(int i=0;i<size;i++){
                Integer p = queue.poll();
                valStart[p]=v;
                //下一层的所有节点入队列
                Set<Integer> chs = graph[p];
                for (Integer ch : chs) {
                    if(!visited[ch]){
                        visited[ch]=true;
                        queue.add(ch);
                    }
                }
            }
            //进入下一层，距离加一
            v++;
        }
        return valStart;
    }

    /**
     * 邻接表建图
     * @param edges 边
     */
    public void createGraph(int[][]edges){
        graph=new HashSet[edges.length+1];
        for(int i=1;i<graph.length;i++){
            graph[i]=new HashSet<>();
        }
        for (int[] edge : edges) {
            int i=edge[0];
            int j=edge[1];
            graph[i].add(j);
            graph[j].add(i);
        }
    }
}

python3 解法, 执行用时: 440 ms, 内存消耗: 72.7 MB, 提交时间: 2023-10-27 22:32:01 

class Solution:
    def chaseGame(self, edges: List[List[int]], startA: int, startB: int) -> int:
        n = max(max(i) for i in edges)
        grid = [set() for i in range(n + 1)]
        for i, j in edges:
            grid[i].add(j)
            grid[j].add(i)
        
        def bfs(start):
            res = [-1] * (n + 1)
            que = collections.deque([start])
            res[start] = 0
            while que:
                p = que.popleft()
                for i in grid[p]:
                    if res[i] == -1:
                        res[i] = res[p] + 1
                        que.append(i)
            return res
        la, lb = bfs(startA), bfs(startB)
        if la[startB] == 1: return 1
        res = 1
        for i, j in zip(la, lb):
            if i - j > 1:
                res = max(res, i)
        que = []
        for i in range(1, n + 1):
            if len(grid[i]) == 1:
                que.append(i)
        while que:
            x = que.pop()
            for i in grid[x]:
                grid[i].remove(x)
                if len(grid[i]) == 1:
                    que.append(i)
            grid[x].pop()
        que = []
        for i in range(1, n + 1):
            if len(grid[i]) > 1:
                que.append(i)
        def dfs(start, leave, pre, target):
            if leave == 0: return True
            for i in grid[start]:
                if i == pre: continue
                if i == target: return False
                if not dfs(i, leave-1, start, target):
                    return False
            return True
        for i in que:
            if la[i] - lb[i] < 2: continue
            if dfs(i, 3, -1, i):
                return -1
        return res

cpp 解法, 执行用时: 332 ms, 内存消耗: 131.8 MB, 提交时间: 2023-10-27 22:31:46 

class Solution {
private:
    vector<vector<int>> m;          // 邻接表存图
    vector<int> circle;             // 判断点是否在环中，0为不在环中，1为在环中
    int n,circle_size;              // 点的个数和环中点的个数
public:
    // 调用深搜函数找环
    void find_circle() {
        vector<int> vis(m.size());
        stack<int> path;
        dfs(1, -1, vis, path);
    }

    /* 
        深搜找环，now是当前访问的点，frm是深搜过程中上一个点
        vis标记点的访问情况，path是当前深搜的路径
    */
    bool dfs(int now, int frm, vector<int> &vis, stack<int> &path) {
        
        // 当前搜索到的点已经被访问过了，出现闭环，记录答案
        if (vis[now]) {
            circle[now] = 1;
            while (! path.empty() && now != path.top()) {
                int tmp = path.top();
                path.pop();
                circle[tmp] = 1;
            }
            return true;
        }

        vis[now] = 1;
        path.push(now);
        for (int i = 0; i < m[now].size(); i ++) {
            if (m[now][i] != frm) {
                if (dfs(m[now][i], now, vis, path)) return true;
            }
        }
        path.pop();
        vis[now] = 0;
        return false;
    }

    // 广搜计算A和B点与图中其他点的距离
    vector<int> bfs(int start) {
        queue<pair<int, int>> q;
        vector<int> vis(m.size(), 0), ans(m.size(), 0);
        q.push({start, 0});
        vis[start] = 1;
        while (! q.empty()) {
            int tmp = q.front().first;
            int dis = q.front().second;
            ans[tmp] = dis;
            q.pop();
            for (int i = 0; i < m[tmp].size(); i ++) {
                if (! vis[m[tmp][i]]) {
                    vis[m[tmp][i]] = 1;
                    q.push({m[tmp][i], dis + 1});
                }
            }
        }
        return ans;
    }

    // 判断B是否可以安全进入环中
    bool get_enterance_dis(vector<int> &disa, vector<int> &disb) {
        int ans = 0;
        // 遍历环的每一个入口，计算A和B的距离差，距离差大于1，说明B可以安全进入环
        for (int i = 1; i < m.size(); i ++) {
            if (m[i].size() > 2 && circle[i] && disa[i] - disb[i] > 1) {
                return true;
            }
        }
        return false;
    }

    int chaseGame(vector<vector<int>>& edges, int startA, int startB) {
        n = edges.size();
        circle_size = 0;
        m = vector<vector<int>>(n+1);
        circle = vector<int> (m.size()+1);

        // 邻接表存无向图
        for ( int i = 0; i < n; i ++) {
            m[edges[i][0]].push_back(edges[i][1]);
            m[edges[i][1]].push_back(edges[i][0]);
        }

        // 找到图中环，以及环中点的个数
        find_circle();
        for (int i = 1;i < circle.size(); i ++) {
            if (circle[i] > 0) circle_size ++;
        }

        // 分别计算A和B与图中各点的距离
        vector<int> disa = bfs(startA);
        vector<int> disb = bfs(startB);

        // 求B可以到达最远的安全点（maxn）
        int maxn = 0;
        for (int i = 1;i <= n; i ++) {
            if (disa[i] - disb[i] > 1 && disa[i] > disa[maxn]) maxn = i;
        }

        // 不存在安全点，即A和B相邻
        if (maxn == 0) return 1;

        // 环中点数等于3，A必能追上B
        if (circle_size==3) return disa[maxn];
        // 环中点数大于等于4
        else {
            // 如果B本身就在环中，保持在环中移动即可逃脱
            if (circle[startB]) return -1;
            // 判断环中是否存在一个安全的入口，使B可以安全进入环中
            else{
                if (get_enterance_dis(disa, disb)) return -1;
                else return disa[maxn];
            }
        }
        return 0;
    }
};

cpp 解法, 执行用时: 368 ms, 内存消耗: 147.8 MB, 提交时间: 2023-10-27 22:31:31 

#define INF 0x3f3f3f3f

class Solution {
    vector<vector<int>> adj;
    vector<int> depth, parent;
    vector<bool> in_loop;
    int n, loop = 0;
    void dfs(int u, int p) {
        parent[u] = p;
        depth[u] = depth[p] + 1;
        for (int v : adj[u]) {
            if (v == p)
                continue;
            if (!depth[v]) 
                dfs(v, u);
            else if (depth[v] < depth[u]) {
                // 发现反向边，说明找到了环
                int cu = u;
                while (cu != v) {
                    in_loop[cu] = true;
                    loop++;
                    cu = parent[cu];
                }
                in_loop[v] = true;
                loop++;
            }
        }
    }
    
    vector<int> bfs(int u, bool detect_loop) {
        // detect_loop为标志位，为true表示BFS的目标是找到环的入口
        // 如果detect_loop为false，表示BFS的目标是求出到所有点的最短距离
        vector<int> dist(n + 1, INF);
        queue<int> q;
        dist[u] = 0;
        q.push(u);
        while (!q.empty()) {
            int x = q.front();
            q.pop();
            if (detect_loop && in_loop[x])
                return {x, dist[x]};
            for (int y : adj[x]) {
                if (dist[y] <= dist[x] + 1)
                    continue;
                dist[y] = dist[x] + 1;
                q.push(y);
            }
        }
        return dist;
    }
public:
    int chaseGame(vector<vector<int>>& edges, int startA, int startB) {
        n = edges.size();
        adj = vector<vector<int>>(n + 1);
        for (auto v : edges) {
            adj[v[0]].emplace_back(v[1]);
            adj[v[1]].emplace_back(v[0]);
            // 如果两个人一开始就相邻，第一回合就能抓住
            if (v[0] == startA && v[1] == startB)
                return 1;
            if (v[0] == startB && v[1] == startA)
                return 1;
        }
        
        // DFS找环
        depth = vector<int>(n + 1);
        parent = vector<int>(n + 1);
        in_loop = vector<bool>(n + 1);
        dfs(1, 0);
        
        // BFS求出A和B到所有点的最短距离
        vector<int> da = bfs(startA, false);
        vector<int> db = bfs(startB, false);
        
        // 如果环的长度大于等于4，那么存在B永远无法被捉到的可能性
        if (loop >= 4) {
            // 寻找B到环的入口（可能就是B本身），及距离
            vector<int> qb = bfs(startB, true);
            // 如果A到B的入口的距离大于B到环的入口距离加一，则B可以永远不被捉到
            if (qb[1] + 1 < da[qb[0]])
                return -1;
        }
        
        // A一定可以捉到B，B要使自己尽可能晚被捉到
        int ans = 0;
        for (int i = 1; i <= n; ++i)
            // 如果一个点到A的最短距离大于到B的最短距离加一
            // 这个点就是B可以安全到达的点
            // 用它更新最后的结果
            if (da[i] > db[i] + 1)
                ans = max(ans, da[i]);
        return ans;
    }
};

上一题

© 2024 leetcode.cn