主页 / coding / 问题 / 79599973
Accepted
MaxH
Asked: 2025-04-30 17:11:28 +0800 CST

如何加速 Leetcode 2290“到达拐角的最小障碍物移除量”的代码

  • 772

我正在解决一些 leetcode 问题。但是对于这个难题，我不知道如何进一步加快我的算法速度。

https://leetcode.com/problems/minimum-obstacle-removal-to-reach-corner/submissions/1621824895

public class Solution {

    public int MinimumObstacles(int[][] grid) {
        int m = grid.Length;
        int n = grid[0].Length;
        var field = new MyDict(m, n, grid);
        field[(0,0)].wallsToHere = 0;
        List<Cell> toDo = [field[(0,0)]];
        while(!toDo.Contains(field[(m-1,n-1)])){
            var c = toDo.OrderBy(x=>x.wallsToHere).First();
            try{
                var testC = field[(c.m-1,c.n)];
                CheckCell(testC, c, toDo);
            }catch{}
            try{
                var testC = field[(c.m+1,c.n)];
                CheckCell(testC, c, toDo);
            }catch{}
            try{
                var testC = field[(c.m,c.n-1)];
                CheckCell(testC, c, toDo);
            }catch{}
            try{
                var testC = field[(c.m,c.n+1)];
                CheckCell(testC, c, toDo);
            }catch{}
            toDo.Remove(c);
            c.done = true;
        }
        return field[(m-1,n-1)].wallsToHere;
    }

    private void CheckCell(Cell testC, Cell c, List<Cell> toDo){
        if(!toDo.Contains(testC) && !testC.done){
            if (testC.wallsToHere > c.wallsToHere + testC.value){
                testC.wallsToHere = c.wallsToHere + testC.value;
            }
            toDo.Add(testC);
        }
    }
}

public class Cell(int value, int m, int n){
    public int value = value;
    public int wallsToHere = (int)Math.Pow(10,5)+1;
    public int m = m;
    public int n = n;
    public bool done = false;
}

public class MyDict:Dictionary<(int,int),Cell>
{
    public MyDict(int m, int n, int[][] grid){
        this.m=m;
        this.n=n;
        this._grid = grid;
    }

    private int m;
    private int n;
    private int[][] _grid;

    public new Cell this[(int,int) key]{
        get{
            if (base.Keys.Contains(key)){
                return base[key];
            }
            else if (key.Item1 < 0 || key.Item2 < 0 || key.Item1 > m || key.Item2 > n){
                throw new Exception();
            }
            else{
                Cell c = new Cell(_grid[key.Item1][key.Item2], key.Item1, key.Item2);
                base[key] = c;
                return c;
            }
        }
    }
}

除了我的 MyDict 实现之外，我不确定如何使用我的 Dijkstra 方法更快地解决这个问题。

如果可能的话，我怎样才能加快速度并改进，而不使用其他方法？

c#

1 个回答

  1. Best Answer

    TL;DR

    使用 0-1 广度优先搜索 (BFS)（或者至少使用带有真正优先级队列的 Dijkstra 算法）。
    你当前的代码每次循环都会OrderBy调用一个增长List函数，所以内层循环的复杂度是 O(k log k) 而不是 O(1)——这就是为什么它感觉很慢。

    采用 (0-1 BFS) 方法（又称Dijkstra，边权重为 0/1）

    using System.Collections.Generic;

public class Solution
{
    public int MinimumObstacles(int[][] grid)
    {
        int m = grid.Length, n = grid[0].Length;
        var dist = new int[m, n];
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                dist[i, j] = int.MaxValue;
        dist[0, 0] = 0;

        // LinkedList<T> gives O(1) AddFirst / AddLast / RemoveFirst
        var dq = new LinkedList<(int r, int c)>();
        dq.AddFirst((0, 0));

        int[] dr = { 1, -1, 0, 0 };
        int[] dc = { 0, 0, 1, -1 };

        while (dq.Count > 0)
        {
            var (r, c) = dq.First!.Value;
            dq.RemoveFirst();

            if (r == m - 1 && c == n - 1)            // reached target
                return dist[r, c];

            for (int k = 0; k < 4; ++k)
            {
                int nr = r + dr[k], nc = c + dc[k];
                if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;

                int cost = dist[r, c] + grid[nr][nc]; // +1 if obstacle, else +0
                if (cost < dist[nr, nc])
                {
                    dist[nr, nc] = cost;
                    if (grid[nr][nc] == 0)
                        dq.AddFirst((nr, nc));       // weight 0 → front
                    else
                        dq.AddLast((nr, nc));        // weight 1 → back
                }
            }
        }
        return -1;   // grid is always reachable per problem statement
    }
}

    为什么它很快

    • 0-1 BFS是 Dijkstra 算法，专门针对边权重 0 或 1。
      移入0单元格的成本为 0 → 向前推；移入1单元格的成本为 1 → 向后推。

    • 每个单元最多进入双端队列两次⇒O （m×n）时间和O（m×n）空间。

    • 热循环中没有排序，没有异常。

    是什么导致原始代码运行缓慢

    • 每次迭代都执行 toDo.OrderBy(...).First() 。对k个项目进行完整排序 ⇒每次弹出Θ(k log k) ；最坏情况下，整体排序结果为O(V² log V) 。

    • 每次添加之前都要执行 toDo.Contains(...) 操作。再次进行 O(k) 线性扫描。

    底线

    替换List + OrderBy为

    • 0-1 BFS（双端队列），当权重只有 0/1 时——最快、最简单，或者

    • PriorityQueue<TElement,TPriority>（Dijkstra）适用于任意非负权重。

    任何对开放集进行重复排序或线性扫描的操作都会慢一个数量级。

    • 2

相关问题