n×n网格哈密顿路径计数程序优化：is_grid_splitting函数未触发排查

我正在解决n×n网格中从左上角到右下角的哈密顿路径计数问题（路径需访问每个格子恰好一次，例如7×7网格存在111712条此类路径）。已经实现了可运行的程序，并且做了这些优化：

• 对称优化：第一步固定向右走，最终结果乘以2
• 提前终止：未遍历所有格子就到达终点则直接返回

现在想实现一种剪枝逻辑：当路径无法继续前进，但左右两侧均存在未访问格子时，网格会被分割为两个都包含未访问格子的区域，此时应该停止该路径的搜索。但我写的is_grid_splitting函数始终不返回true，没法触发剪枝。下面是我的代码，帮忙排查问题原因：

#include <bits/stdc++.h>
using namespace std;

const int n = 5;
vector<vector<int>> grid(n, vector<int>(n, 0));
int paths = 0;
vector<vector<bool>> visited(n, (vector<bool>(n, false)));
int last_turn;

bool is_valid(int x, int y) {
    return x >=0 && x < n && y >= 0 && y < n && !visited[x][y]; 
}

bool is_grid_splitting(int x, int y) {
    if (last_turn == 1) {
        if (is_valid(x, y+1) && visited[x][y+1]
        && is_valid(x-1, y) && !visited[x-1][y] 
        && is_valid(x+1, y) && !visited[x+1][y]) 
        {return true;}
    }

    if (last_turn == 2) {
        if (is_valid(x+1, y) && visited[x+1][y]
        && is_valid(x, y-1) && !visited[x][y-1]
        && is_valid(x, y+1) && !visited[x][y+1])
        {return true;}
    }

    if (last_turn == 3) {
        if (is_valid(x, y-1) && visited[x][y-1]
        && is_valid(x-1, y) && !visited[x-1][y]
        && is_valid(x+1, y) && !visited[x+1][y])
        {return true;}
    }

    if (last_turn == 4) {
        if (is_valid(x-1,y) && visited[x-1][y]
        && is_valid(x, y-1) && !visited[x][y-1]
        && is_valid(x, y+1) && !visited[x][y+1])
        {return true;}
    }

    return false;
}

void path(int x, int y, int count) {
    if (x == n-1 && y == n-1 && count == n * n) {paths++; return;}

    if (x == n-1 && y == n-1) {return;}
    
    if (!is_grid_splitting(x, y)) {
        visited[x][y] = true;

        if (is_valid(x, y+1)) {
            last_turn = 1;
            path(x, y+1, count + 1);
        }

        if (is_valid(x+1, y)) {
            last_turn = 2;
            path(x+1, y, count + 1);
        }

        if (is_valid(x, y-1)) {
            last_turn = 3;
            path(x, y-1, count + 1);
        }

        if (is_valid(x-1, y)) {
            last_turn = 4;
            path(x-1, y, count + 1);
        }

        visited[x][y] = false;
    } else {return;}   
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    last_turn = 3;
    visited[0][0] = true;
    path(0, 1, 2);

    paths *= 2;
    cout << paths;
}

问题核心原因及修复方案 #

1. is_valid函数的逻辑矛盾

你的is_valid函数定义是仅当格子未被访问时返回true，但在is_grid_splitting中却写了is_valid(x, y+1) && visited[x][y+1]——这两个条件永远不可能同时成立，直接导致所有分割判断都为false，函数永远返回false。

2. 剪枝时机错误

你在标记当前格子为已访问前就调用了is_grid_splitting，此时当前格子的访问状态未更新，分割判断基于错误的网格状态，自然无法触发剪枝。

3. 全局变量last_turn的状态混乱

last_turn是全局变量，递归调用时会被覆盖，回溯时无法恢复之前的方向状态，导致分割判断的方向逻辑完全错误。

修复后的关键代码示例 #

修正is_grid_splitting函数

直接使用visited数组判断状态，不再依赖is_valid：

bool is_grid_splitting(int x, int y, int last_dir) {
    // last_dir: 1=右, 2=下, 3=左, 4=上
    if (last_dir == 1) { // 最后一步向右走，来自(x,y-1)
        bool back_visited = (y-1 >= 0) && visited[x][y-1];
        bool up_unvisited = (x-1 >= 0) && !visited[x-1][y];
        bool down_unvisited = (x+1 < n) && !visited[x+1][y];
        return back_visited && up_unvisited && down_unvisited;
    }
    if (last_dir == 2) { // 最后一步向下走，来自(x-1,y)
        bool back_visited = (x-1 >= 0) && visited[x-1][y];
        bool left_unvisited = (y-1 >= 0) && !visited[x][y-1];
        bool right_unvisited = (y+1 < n) && !visited[x][y+1];
        return back_visited && left_unvisited && right_unvisited;
    }
    if (last_dir == 3) { // 最后一步向左走，来自(x,y+1)
        bool back_visited = (y+1 < n) && visited[x][y+1];
        bool up_unvisited = (x-1 >= 0) && !visited[x-1][y];
        bool down_unvisited = (x+1 < n) && !visited[x+1][y];
        return back_visited && up_unvisited && down_unvisited;
    }
    if (last_dir == 4) { // 最后一步向上走，来自(x+1,y)
        bool back_visited = (x+1 < n) && visited[x+1][y];
        bool left_unvisited = (y-1 >= 0) && !visited[x][y-1];
        bool right_unvisited = (y+1 < n) && !visited[x][y+1];
        return back_visited && left_unvisited && right_unvisited;
    }
    return false;
}

调整递归函数的剪枝时机与方向传递

把last_dir作为参数传递，先标记当前格子再做剪枝判断：

void path(int x, int y, int count, int last_dir) {
    if (x == n-1 && y == n-1) {
        if (count == n * n) paths++;
        return;
    }
    
    visited[x][y] = true;
    
    if (!is_grid_splitting(x, y, last_dir)) {
        if (is_valid(x, y+1)) path(x, y+1, count+1, 1);
        if (is_valid(x+1, y)) path(x+1, y, count+1, 2);
        if (is_valid(x, y-1)) path(x, y-1, count+1, 3);
        if (is_valid(x-1, y)) path(x-1, y, count+1, 4);
    }
    
    visited[x][y] = false;
}

修正main函数的初始调用

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    visited[0][0] = true;
    path(0, 1, 2, 1); // 第一步向右走，方向标记为1

    paths *= 2;
    cout << paths;
}

内容的提问来源于stack exchange，提问作者ABC