‹ 上一题 下一题 ›

g6-07105. 网格回溯·漏撤销 未做

1000 ms 256 MB 测试点 ? 自拟题知识点题GESP-66级·深度优先搜索客观题单选

小酷抄数路线的回溯骨架时,漏抄了「撤销选择」那一行(它本应写在 for 循环结束之后、return 之前):

int dfs(int x, int y) {
    if (x == n - 1 && y == m - 1) return 1;   // 踩到终点:收下这一条
    vis[x][y] = true;                         // 做选择:踏上这格
    int total = 0;
    for (int d = 0; d < 4; d++) { /* 四个方向:合法才 total += dfs(...) */ }
    return total;                             // 这里之前少了一行
}

在一张家门口到右下角、全是空地的 地图上(正确答案 12 种)跑这版代码,结果会( )。

  • A. 绝大多数路线被误判「此路不通」,输出从 12 骤减、甚至归零
  • B. 输出比 12 大,因为格子不再受限制
  • C. 照样输出 12,撤销只是个好习惯,可有可无
  • D. 编译报错,程序跑不起来
未选择
输入
输出

            
答案