优化C#动态规划相关代码：寻求性能提升方案

我完成了老师布置的任务，编写的C#代码可正常运行，在测试区提交后表现尚可，但我知道可通过一些简单却关键的性能优化来拿到满分，却不清楚具体优化点，希望得到帮助。

注：代码中的变量为非英语命名，望谅解。

using System;
using System.Collections.Generic;
using System.Linq;

class Program {
    // Koriscene ASCII vrednosti
    enum Polja { prepreka = 120, praznina = 46, putanja = 1 }
    static HashSet<int> gotoviIndeksi = new HashSet<int>();

    static void RekurzivnoCitanje(List<Polja[]> ispodProzora) {
        var str = Console.ReadLine();
        if (str != null) {
            ispodProzora.Add(str.Select(c => (Polja)c).ToArray());
            RekurzivnoCitanje(ispodProzora);
        }
        else return;
    }

    static bool ValidnoPolje(int i, int j, List<Polja[]> trenutnoStanje) {
        return i >= 0 && i < trenutnoStanje.Count && j >= 0 &&
            j < trenutnoStanje[i].Length && trenutnoStanje[i][j] == Polja.praznina;
    }

    static Tuple<int, int>[] mogucnosti = new Tuple<int, int>[3] {
        new Tuple<int, int>(0, 1),
        new Tuple<int, int>(0, -1),
        new Tuple<int, int>(1, 0)
    };

    static void Popunjavanje(int i, int j, List<Polja[]> trenutnoStanje, int pocetno) {
        if (!ValidnoPolje(i, j, trenutnoStanje)) { return; }

        trenutnoStanje[i][j] = Polja.putanja;
        if(i == trenutnoStanje.Count - 1) {
            gotoviIndeksi.Add(pocetno);
            return;
        }

        if (trenutnoStanje[i + 1][j] == Polja.prepreka) {
            Popunjavanje(i + mogucnosti[0].Item1, j + mogucnosti[0].Item2, trenutnoStanje, pocetno);
            Popunjavanje(i + mogucnosti[1].Item1, j + mogucnosti[1].Item2, trenutnoStanje, pocetno);
        }
        else if (trenutnoStanje[i + 1][j] == Polja.praznina) {
            Popunjavanje(i + mogucnosti[2].Item1, j + mogucnosti[2].Item2, trenutnoStanje, pocetno);
        }
    }

    static void Main() {
        var ispodProzora = new List<Polja[]>();
        RekurzivnoCitanje(ispodProzora);

        for (int i = 0; i < ispodProzora[0].Length; i++) {
            Popunjavanje(0, i, ispodProzora.Select(array => array.ToArray()).ToList(), i);
        }
        for(int i = 0; i < ispodProzora[0].Length; i++) {
            Console.Write(gotoviIndeksi.Contains(i) ? 1 : 0);
        }
        Console.ReadLine();
    }
}

关键性能优化点 #

• 避免重复复制地图：原代码每次遍历起点时都完整复制整个地图，这是最大的性能瓶颈。改用回溯法：使用一份原始地图副本，在递归访问时标记路径，退出递归时恢复标记，彻底消除复制开销。
• 替换递归为迭代搜索：递归深度超过一定值会触发栈溢出，且递归调用本身有额外开销。用Stack实现迭代式深度优先搜索（DFS），更稳定高效。
• 用布尔数组替代HashSet：对于连续的起点索引，bool[]的访问速度比HashSet<int>更快，内存占用也更紧凑，直接通过索引判断是否可达。
• 优化输入读取：递归读取输入存在栈溢出风险，改用循环读取所有输入行，更安全高效。
• 减少类型转换开销：直接使用字符或整数代替枚举Polja，避免频繁的类型装箱/拆箱操作。
• 提前终止无效搜索：一旦某个起点已确认可达终点，后续无需再处理；搜索过程中若已到达终点，可直接标记并返回，减少不必要的递归/迭代。

优化后示例代码（核心修改） #

using System;
using System.Collections.Generic;
using System.Linq;

class Program {
    const char Prepreka = 'x';
    const char Praznina = '.';
    const char Putanja = '1';
    static bool[] gotoviIndeksi;
    static char[][] mapa;
    static int visina, sirina;

    static void Main() {
        // 循环读取输入，替代递归读取
        var lines = new List<string>();
        string line;
        while ((line = Console.ReadLine()) != null) {
            lines.Add(line);
        }
        visina = lines.Count;
        sirina = lines[0].Length;
        mapa = lines.Select(l => l.ToCharArray()).ToArray();
        gotoviIndeksi = new bool[sirina];

        // 对每个起点进行DFS搜索
        for (int j = 0; j < sirina; j++) {
            if (mapa[0][j] == Praznina) {
                Dfs(0, j, j);
            }
        }

        // 输出结果
        foreach (bool dostupan in gotoviIndeksi) {
            Console.Write(dostupan ? "1" : "0");
        }
        Console.ReadLine();
    }

    static void Dfs(int i, int j, int pocetno) {
        // 边界与有效性检查
        if (i < 0 || i >= visina || j < 0 || j >= sirina || mapa[i][j] != Praznina) {
            return;
        }

        // 标记当前路径
        mapa[i][j] = Putanja;

        // 到达终点，标记起点为可达
        if (i == visina - 1) {
            gotoviIndeksi[pocetno] = true;
            // 恢复标记，继续搜索其他路径
            mapa[i][j] = Praznina;
            return;
        }

        // 优先向下走
        if (mapa[i + 1][j] == Praznina) {
            Dfs(i + 1, j, pocetno);
        }
        // 遇到障碍物则左右走
        else if (mapa[i + 1][j] == Prepreka) {
            Dfs(i, j + 1, pocetno);
            Dfs(i, j - 1, pocetno);
        }

        // 回溯，恢复当前位置状态
        mapa[i][j] = Praznina;
    }
}

内容的提问来源于stack exchange，提问作者Nikola Savić