哈密顿回路、链路、其他点覆盖问题

目录

一，哈密顿回路、哈密顿链路

二，相关定理

1，Dirac定理

2，Tutte定理

3，竞赛图必有哈密顿链路

三，应用

1，旅行商问题（TSP）

2，芯片通孔

四，相关puzzle

1，数字满格、数阵迷踪、数字迷途、数字连线

2，踏马、立方骑士

3，矩形图中马的哈密顿回路、链路

五，点的回路覆盖问题

1，回路覆盖问题

2，相关定理

3，应用

六，最短哈密顿链路

1，不指定起点和终点

2，只指定起点

3，只指定终点

4，指定起点和终点

5，汇总模板

6，力扣实战（模板）

力扣 943. 最短超级串（不指定起点和终点）

力扣 LCP 13. 寻宝（指定起点和终点）

7，力扣实战（非模板）

力扣 996. 正方形数组的数目

力扣 980. 不同路径 III

一，哈密顿回路、哈密顿链路

图的哈密顿回路是指包含图的所有节点的回路。

图的哈密顿链路是指包含图的所有节点的链路。

二，相关定理

1，Dirac定理

如果G是一个n（n≥3）个点的无向简单图，所有节点的度数都 ≥ n/2.0，则G中存在哈密顿回路。

证明过程：

（1）G是连通图

（2）设最长路径是L，用抽屉原理可以证明L是个环

（3）如果有节点不在环中，根据连通性可以加入一个点把环变成一条更长的路径。所以所有节点都在这个环中。

2，Tutte定理

所有4连通平面图都有哈密顿圈。证明过程没研究。

关于平面图，参考常见的图

3，竞赛图必有哈密顿链路

关于竞赛图，参考常见的图

竞赛图中不存在环当且仅当所有顶点的出度从小到大排列依次为0, 1, 2, … , n-1 。

翻译成赛事语言就是，单循环赛结果没有环，当且仅当所有人的实力是线性排序的，没有任何一次比赛发生逆袭现象。

三，应用

1，旅行商问题（TSP）

给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。

这是NP难问题。

2，芯片通孔

芯片上有很多不同尺寸的通孔，用于走线。

同一尺寸的通孔用1个钻头全部打完之后，再换钻头。

对于1个钻头来说，如何走最短的距离把所有通孔打完？

四，相关puzzle

1，数字满格、数阵迷踪、数字迷途、数字连线

数字满格、数阵迷踪、数字迷途、数字连线

2，踏马、立方骑士

踏马、立方骑士

3，矩形图中马的哈密顿回路、链路

定理：

如果n是偶数（n>4）那么n*n的棋盘有一个哈密顿回路。

如果n是奇数（n>3）那么n*n的棋盘有一个哈密顿链路。

像这样的图还可以构造一些，不过基本上都差不多。

总结起来就是，最中间的格子是比较特殊的，上图中标号1-8的这8个格子构成1个回路，

其余的16个格子也构成1个回路，相当于5*5的棋盘其实就是3个回路组合而成，只要适当地选择断点，即可把3个回路连接成一条链。

如果选取的起点不同，得到的哈密顿链还是略有区别的。

比如：112象棋（12）

关于上面的2个定理，书上的意思是用数学归纳法来证明，从n=k变成n=k+4相当于在原来的基础上，套上了一个宽度为2的边框。这个边框是若干个哈密顿回路组成的，只要在适当的地方断开，就可以和里面的k*k连接起来。

下面讨论，7*7的棋盘去掉中间的3*3如何形成哈密顿回路。

首先，角落的点只有2个邻居，那么在回路里面，这2个点也一定都是他的邻居。

其他的，以此类推，可以得到下图：

对于那些已经连了2条线的点，自然是没有任何悬念了，所以接下来只需要考虑那些恰好连了1条线的点该如何连接起来。将上图化简如下：

黑色的线表示一定相连，红色的线表示可能相连。

这样，可以得到这16个点的哈密顿回路：

与此对应，可以得到原图：

这是由2个哈密顿回路构成的。

这样，整个通过把大的回路断开一个地方，可以得到下图：

在把紫色的哈密顿回路和这个长为41的哈密顿链连接起来，即可得到7*7的哈密顿链

五，点的回路覆盖问题

1，回路覆盖问题

对于没有割边的图，求一组简单回路，覆盖所有的点，且总边数最少。

2，相关定理

n个点的无割边图，存在一组简单回路，覆盖所有的点，且总边数不超过2n-2

3，应用

如果按照这个方式建设网络，就能得到边数很少的无割边图。

无割边意味着至少是2连通，比普通的连通图稳定性更好。

六，最短哈密顿链路

对于有向图，求所有的哈密顿链路中，长度最短的那条。

1，不指定起点和终点

思路：状态压缩DP

时间复杂度：O（n^2 * 2^n）

//最短哈密顿链路 template<typename T = int> class MinHamilton { public: MinHamilton(int n, DirectedGraphData<T>& g) :g(g) //n的上限大概是15 { this->n = n; startId = g.getStartId(); m.clear(); path.clear(); } vector<int> getMinPath() //返回0到n-1的排序 { int allId = (1 << n) - 1; int ans = INT_MAX; for (int i = 0; i < n; i++) { ans = min(ans, dp(i, allId ^ (1 << i))); } for (int i = 0; i < n; i++) { if (m[i][allId ^ (1 << i)] == ans) { reBuild(i, allId ^ (1 << i), ans); return path; } } return vector<int>{}; } private: int dp(int id, int allOtherId) { auto& mi = m[id]; if (mi.find(allOtherId) != mi.end())return mi[allOtherId]; if (!allOtherId)return mi[allOtherId] = 0; int ans = INT_MAX; for (int i = 0; i < n; i++) { if ((allOtherId & (1 << i)) == 0)continue; auto it = g.edgeMap.find(make_pair(startId + id, startId + i)); if (it == g.edgeMap.end())continue; int x = dp(i, allOtherId ^ (1 << i)); if (x < INT_MAX)ans = min(ans, x + it->second); } return mi[allOtherId] = ans; } void reBuild(int id, int allOtherId, int ans) { path.push_back(id); if (!allOtherId)return; for (int i = 0; i < n; i++) { if ((allOtherId & (1 << i)) == 0)continue; auto it = g.edgeMap.find(make_pair(startId + id, startId + i)); if (it == g.edgeMap.end())continue; if (m[i][allOtherId ^ (1 << i)] == ans - it->second) { return reBuild(i, allOtherId ^ (1 << i), ans - it->second); } } } private: DirectedGraphData<T>& g; int n; int startId; map<int, map<int, int>>m; vector<int>path; };

2，只指定起点

//最短哈密顿链路 template<typename T = int> class MinHamilton { public: MinHamilton(int n, DirectedGraphData<T>& g, int startLoc) :g(g) //n的上限大概是15 { this->n = n; startId = g.getStartId(); this->startLoc = startLoc - startId; m.clear(); path.clear(); } vector<int> getMinPath() //返回0到n-1的排序 { int allId = (1 << n) - 1; int ans = dp(startLoc, allId ^ (1 << startLoc)); reBuild(startLoc, allId ^ (1 << startLoc), ans); return path; } private: int dp(int id, int allOtherId) { auto& mi = m[id]; if (mi.find(allOtherId) != mi.end())return mi[allOtherId]; if (!allOtherId)return mi[allOtherId] = 0; int ans = INT_MAX; for (int i = 0; i < n; i++) { if ((allOtherId & (1 << i)) == 0)continue; auto it = g.edgeMap.find(make_pair(startId + id, startId + i)); if (it == g.edgeMap.end())continue; int x = dp(i, allOtherId ^ (1 << i)); if (x < INT_MAX)ans = min(ans, x + it->second); } return mi[allOtherId] = ans; } void reBuild(int id, int allOtherId, int ans) { path.push_back(id); if (!allOtherId)return; for (int i = 0; i < n; i++) { if ((allOtherId & (1 << i)) == 0)continue; auto it = g.edgeMap.find(make_pair(startId + id, startId + i)); if (it == g.edgeMap.end())continue; if (m[i][allOtherId ^ (1 << i)] == ans - it->second) { return reBuild(i, allOtherId ^ (1 << i), ans - it->second); } } } private: DirectedGraphData<T>& g; int n; int startId; int startLoc; map<int, map<int, int>>m; vector<int>path; };

3，只指定终点

把起点和终点互换，把图变成反图，即可转化成只指定起点的场景。

4，指定起点和终点

//最短哈密顿链路 template<typename T = int> class MinHamilton { public: MinHamilton(int n, DirectedGraphData<T>& g, int startLoc,int targetLoc) :g(g) //n的上限大概是15 { this->n = n; startId = g.getStartId(); this->startLoc = startLoc - startId; this->targetLoc = targetLoc - startId; m.clear(); path.clear(); } vector<int> getMinPath(int &ans) //返回0到n-1的排序 { int allId = (1 << n) - 1; ans = dp(startLoc, allId ^ (1 << startLoc) ^ (1 << targetLoc)); reBuild(startLoc, allId ^ (1 << startLoc) ^ (1 << targetLoc), ans); return path; } private: int dp(int id, int allOtherId) { auto& mi = m[id]; if (mi.find(allOtherId) != mi.end())return mi[allOtherId]; if (!allOtherId) { auto it = g.edgeMap.find(make_pair(startId + id, startId + targetLoc)); if (it == g.edgeMap.end())return mi[allOtherId] = INT_MAX; return mi[allOtherId] = it->second; } int ans = INT_MAX; for (int i = 0; i < n; i++) { if ((allOtherId & (1 << i)) == 0)continue; auto it = g.edgeMap.find(make_pair(startId + id, startId + i)); if (it == g.edgeMap.end())continue; int x = dp(i, allOtherId ^ (1 << i)); if (x < INT_MAX)ans = min(ans, x + it->second); } return mi[allOtherId] = ans; } void reBuild(int id, int allOtherId, int ans) { path.push_back(id); if (!allOtherId) { path.push_back(targetLoc); return; } for (int i = 0; i < n; i++) { if ((allOtherId & (1 << i)) == 0)continue; auto it = g.edgeMap.find(make_pair(startId + id, startId + i)); if (it == g.edgeMap.end())continue; if (m[i][allOtherId ^ (1 << i)] == ans - it->second) { return reBuild(i, allOtherId ^ (1 << i), ans - it->second); } } } private: DirectedGraphData<T>& g; int n; int startId; int startLoc; int targetLoc; map<int, map<int, int>>m; vector<int>path; };

5，汇总模板

//最短哈密顿链路 template<typename T = int> class MinHamilton { public: MinHamilton(int n, DirectedGraphData<T>& g) :g(g) //n的上限大概是15 { type = 0; this->n = n; startId = g.getStartId(); } MinHamilton(int n, DirectedGraphData<T>& g, int startLoc) :g(g) //如果g的顶点编号是3-6，则startLoc属于[3,6]，且n=4，且startId=3 { type = 1; this->n = n; startId = g.getStartId(); this->startLoc = startLoc - startId; } MinHamilton(int n, DirectedGraphData<T>& g, int startLoc,int targetLoc) :g(g) { type = 2; this->n = n; startId = g.getStartId(); this->startLoc = startLoc - startId; this->targetLoc = targetLoc - startId; } vector<int> getMinPath(int &ans) //返回0到n-1的排序, ans是最短距离 { path.clear(); m.clear(); int allId = (1 << n) - 1; if (type == 2) { ans = dp(startLoc, allId ^ (1 << startLoc) ^ (1 << targetLoc)); reBuild(startLoc, allId ^ (1 << startLoc) ^ (1 << targetLoc), ans); } else if (type == 1) { ans = dp(startLoc, allId ^ (1 << startLoc)); reBuild(startLoc, allId ^ (1 << startLoc), ans); } else { ans = INT_MAX; for (int i = 0; i < n; i++) { ans = min(ans, dp(i, allId ^ (1 << i))); } for (int i = 0; i < n; i++) { if (m[i][allId ^ (1 << i)] == ans) { reBuild(i, allId ^ (1 << i), ans); break; } } } return path; } private: int dp(int id, int allOtherId) { auto& mi = m[id]; if (mi.find(allOtherId) != mi.end())return mi[allOtherId]; if (type == 2) { if (!allOtherId) { auto it = g.edgeMap.find(make_pair(startId + id, startId + targetLoc)); if (it == g.edgeMap.end())return mi[allOtherId] = INT_MAX; return mi[allOtherId] = it->second; } } else { if (!allOtherId)return mi[allOtherId] = 0; } int ans = INT_MAX; for (int i = 0; i < n; i++) { if ((allOtherId & (1 << i)) == 0)continue; auto it = g.edgeMap.find(make_pair(startId + id, startId + i)); if (it == g.edgeMap.end())continue; int x = dp(i, allOtherId ^ (1 << i)); if (x < INT_MAX)ans = min(ans, x + it->second); } return mi[allOtherId] = ans; } void reBuild(int id, int allOtherId, int ans) { path.push_back(id); if (type == 2) { if (!allOtherId) { path.push_back(targetLoc); return; } } else { if (!allOtherId)return; } for (int i = 0; i < n; i++) { if ((allOtherId & (1 << i)) == 0)continue; auto it = g.edgeMap.find(make_pair(startId + id, startId + i)); if (it == g.edgeMap.end())continue; if (m[i][allOtherId ^ (1 << i)] == ans - it->second) { return reBuild(i, allOtherId ^ (1 << i), ans - it->second); } } } private: int type; // 0:不指定起点和终点 1:只指定起点 2:指定起点和终点 DirectedGraphData<T>& g; int n; int startId; int startLoc; int targetLoc; map<int, map<int, int>>m; vector<int>path; };

6，力扣实战（模板）

力扣 943. 最短超级串（不指定起点和终点）

给定一个字符串数组words，找到以words中每个字符串作为子字符串的最短字符串。如果有多个有效最短字符串满足题目条件，返回其中任意一个即可。

我们可以假设words中没有字符串是words中另一个字符串的子字符串。

示例 1：

输入：words = ["alex","loves","leetcode"]输出："alexlovesleetcode"解释："alex"，"loves"，"leetcode" 的所有排列都会被接受。

示例 2：

输入：words = ["catg","ctaagt","gcta","ttca","atgcatc"]输出："gctaagttcatgcatc"

提示：

• 1 <= words.length <= 12
• 1 <= words[i].length <= 20
• words[i]由小写英文字母组成
• words中的所有字符串互不相同

class Solution { public: string shortestSuperstring(vector<string>& words) { if (words.size() == 1)return words[0]; vector<DirectedEdge<>> edges; for (int i = 0; i < words.size(); i++) { for (int j = 0; j < words.size(); j++) { if (i == j)continue; edges.push_back(DirectedEdge<>{vector<int>{i, j, -sameNum(words[i], words[j])}}); } } DirectedGraphData<> g(edges); MinHamilton<> opt(words.size(), g); auto v = opt.getMinPath(); string ans = words[v[0]]; for (int i = 1; i < v.size(); i++) { int len = sameNum(words[v[i - 1]], words[v[i]]); ans += words[v[i]].substr(len, words[v[i]].length() - len); } return ans; } int sameNum(string& s1, string& s2) { int len = min(s1.length(), s2.length()); for (int i = len - 1; i; i--) { if (s1.substr(s1.length() - i, i) == s2.substr(0, i))return i; } return 0; } };

力扣 LCP 13. 寻宝（指定起点和终点）

我们得到了一副藏宝图，藏宝图显示，在一个迷宫中存在着未被世人发现的宝藏。

迷宫是一个二维矩阵，用一个字符串数组表示。它标识了唯一的入口（用 'S' 表示），和唯一的宝藏地点（用 'T' 表示）。但是，宝藏被一些隐蔽的机关保护了起来。在地图上有若干个机关点（用 'M' 表示），只有所有机关均被触发，才可以拿到宝藏。

要保持机关的触发，需要把一个重石放在上面。迷宫中有若干个石堆（用 'O' 表示），每个石堆都有无限个足够触发机关的重石。但是由于石头太重，我们一次只能搬一个石头到指定地点。

迷宫中同样有一些墙壁（用 '#' 表示），我们不能走入墙壁。剩余的都是可随意通行的点（用 '.' 表示）。石堆、机关、起点和终点（无论是否能拿到宝藏）也是可以通行的。

我们每步可以选择向上/向下/向左/向右移动一格，并且不能移出迷宫。搬起石头和放下石头不算步数。那么，从起点开始，我们最少需要多少步才能最后拿到宝藏呢？如果无法拿到宝藏，返回 -1 。

示例 1：

输入： ["S#O", "M..", "M.T"]

输出：16

解释：最优路线为： S->O, cost = 4, 去搬石头 O->第二行的M, cost = 3, M机关触发 第二行的M->O, cost = 3, 我们需要继续回去 O 搬石头。 O->第三行的M, cost = 4, 此时所有机关均触发 第三行的M->T, cost = 2，去T点拿宝藏。 总步数为16。

示例 2：

输入： ["S#O", "M.#", "M.T"]

输出：-1

解释：我们无法搬到石头触发机关

示例 3：

输入： ["S#O", "M.T", "M.."]

输出：17

解释：注意终点也是可以通行的。

限制：

• 1 <= maze.length <= 100
• 1 <= maze[i].length <= 100
• maze[i].length == maze[j].length
• S 和 T 有且只有一个
• 0 <= M的数量 <= 16
• 0 <= O的数量 <= 40，题目保证当迷宫中存在 M 时，一定存在至少一个 O 。

class Solution { public: int minimalSteps(vector<string>& maze) { int s, t; //编号0,1 vector<int> locM; //所有的M, 编号2,3... vector<int> locO; //所有可达的O map<int, int>len; //起点S到其他点的最短距离 bfs(maze, s, t, locM, locO, len); if (locM.empty())return len[t] == 0 ? -1 : len[t]; if (locO.empty())return -1; if (!checkMandT(locM,len,t))return -1; map<int, map<int, int>>m1; //任意M到其他点的最短距离 for (auto id : locM) { m1[id] = bfs(maze, id); } //map<int, map<int, int>>m2; //任意O到其他点的最短距离 map<int, map<int, int>>m3; //任意M或O到任意M的途经O的最短距离 getM3(s,locM,locO,len,m1, m3); vector<DirectedEdge<int>> edges; for (int i = 0; i < locM.size(); i++) { edges.push_back(vector<int>{ 0, i + 2 ,m3[s][locM[i]] }); for (int j = i + 1; j < locM.size(); j++) { edges.push_back(vector<int>{ i + 2, j + 2, m3[locM[i]][locM[j]] }); edges.push_back(vector<int>{ j + 2, i + 2, m3[locM[i]][locM[j]] }); } edges.push_back(vector<int>{ i + 2, 1, m1[locM[i]][t] }); } DirectedGraphData<int> dg(edges); MinHamilton<int> opt(locM.size() + 2, dg, 0, 1); int ans; auto v = opt.getMinPath(ans); return ans; } private: //获取5个出参的值 void bfs(vector<string>& maze, int &s, int &t, vector<int> &locM, vector<int> &locO, map<int, int>&len) { GridGraph g(maze.size(), maze[0].length()); vector<int>v; for (int i = 0; i < maze.size(); i++) { for (int j = 0; j < maze[i].length(); j++) { if (maze[i][j] == 'S')s = g.gridId(i, j); if (maze[i][j] == 'T')t = g.gridId(i, j); if (maze[i][j] == 'M')locM.push_back(g.gridId(i, j)); if (maze[i][j] == 'O')v.push_back(g.gridId(i, j)); } } len = bfs(maze, s); for (auto id : v) { if (len[id])locO.push_back(id); } } map<int, int> bfs(vector<string>& maze, int s) { map<int, int>len; queue<int>q; q.push(s); len[s] = 0; int c = maze[0].length(); GridGraph g(maze.size(), c); while (!q.empty()) { int id = q.front(); q.pop(); auto nbor = g.getNeighbor4(id); for (auto x : nbor) { if (maze[x/c][x%c] != '#' && len.find(x) == len.end()) { len[x] = len[id] + 1; q.push(x); } } } return len; } bool checkMandT(vector<int> &locM, map<int, int>&len, int t) { if (len[t] == 0)return false; for(auto id:locM)if (len[id] == 0)return false; return true; } void getM3(int s, vector<int> &locM, vector<int> &locO, map<int, int>&len, map<int, map<int, int>>&m1, map<int, map<int, int>>&m3) { for (auto id : locM) { for (auto id2 : locM) { int minLen = INT_MAX; for (auto id3 : locO) { minLen = min(minLen, m1[id][id3] + m1[id2][id3]); } m3[id][id2] = minLen; } } int id = s; for (auto id2 : locM) { int minLen = INT_MAX; for (auto id3 : locO) { minLen = min(minLen, len[id3] + m1[id2][id3]); } m3[id][id2] = minLen; } } };

7，力扣实战（非模板）

哈密顿问题其实和TSP问题差不多，是NP问题，没有特别好的算法。

回溯法：

class Hamilton { public: stack<int> hami;//哈密顿链路 Hamilton(int n, map<int, vector<int>>& m, int type)//type=0是无向图 1是有向图 { this->n = n; this->m = m; this->type = type; for (int i = 0; i < n; i++)dfs(i); } private: bool dfs(int k) { s.push(k); if (s.size() == n) { hami = s; return true; } for (auto nk : m[k]) { if (visit[k])continue; visit[k] = 1; if (dfs(nk))return true; visit[k] = 0; } s.pop(); return false; } int n; int type; map<int, vector<int>> m;//邻接表 map<int, int>visit; stack<int>s; };

力扣 996. 正方形数组的数目

给定一个非负整数数组A，如果该数组每对相邻元素之和是一个完全平方数，则称这一数组为正方形数组。

返回 A 的正方形排列的数目。两个排列A1和A2不同的充要条件是存在某个索引i，使得 A1[i] != A2[i]。

示例 1：

输入：[1,17,8]输出：2解释：[1,8,17] 和 [17,8,1] 都是有效的排列。

示例 2：

输入：[2,2,2]输出：1

提示：

1. 1 <= A.length <= 12
2. 0 <= A[i] <= 1e9

vector<int> gnums; class Hamilton { public: map<long long, int>ans; Hamilton(int n, map<int, vector<int>>& m, int type)//type=0是无向图 1是有向图 { this->n = n; this->m = m; this->type = type; for (int i = 0; i < n; i++)dfs(i,1); } private: bool dfs(int k,int deep) { if (visit[k])return false; long long h2 = h; hash(k); if (hashVisit[h]) goto RET; hashVisit[h] = 1; if (deep == n) { ans[h] = 1; h = h2; return true; } visit[k] = 1; for (auto nk : m[k]) { dfs(nk,deep+1); } RET: visit[k] = 0; h = h2; return false; } void hash(int k) { h = ((h * (gnums[k]+123) + 666) * 789)%1000000007; } int n; int type; map<int, vector<int>> m;//邻接表 map<int, int>visit; map<long long, int>hashVisit; long long h = 1234567; }; class Solution { public: int numSquarefulPerms(vector<int>& nums) { int n = nums.size(); map<int, vector<int>>m; for (int i = 0; i < n; i++)for (int j = i + 1; j < n; j++) { if (isSquare(nums[i] + nums[j]))m[i].push_back(j), m[j].push_back(i); } gnums = nums; return Hamilton(n, m, 0).ans.size(); } bool isSquare(int n) { int x = sqrt(n); return x * x == n; } };

力扣 980. 不同路径 III

在二维网格grid上，有 4 种类型的方格：

• 1表示起始方格。且只有一个起始方格。
• 2表示结束方格，且只有一个结束方格。
• 0表示我们可以走过的空方格。
• -1表示我们无法跨越的障碍。

返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目。

每一个无障碍方格都要通过一次，但是一条路径中不能重复通过同一个方格。

示例 1：

输入：[[1,0,0,0],[0,0,0,0],[0,0,2,-1]]输出：2解释：我们有以下两条路径： 1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2) 2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)

示例 2：

输入：[[1,0,0,0],[0,0,0,0],[0,0,0,2]]输出：4解释：我们有以下四条路径： 1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3) 2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3) 3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3) 4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)

示例 3：

输入：[[0,1],[2,0]]输出：0解释：没有一条路能完全穿过每一个空的方格一次。 请注意，起始和结束方格可以位于网格中的任意位置。

提示：

• 1 <= grid.length * grid[0].length <= 20

class Hamilton { public: map<long long, int>ans; Hamilton(int n, map<int, vector<int>>& m, int type,int start,int e)//type=0是无向图 1是有向图 { this->n = n; this->m = m; this->type = type; this->e = e; dfs(start,1); } private: bool dfs(int k,int deep) { if (visit[k])return false; long long h2 = h; hash(k); if (hashVisit[h]) goto RET; hashVisit[h] = 1; if (deep == n) { ans[h] = 1; h = h2; return true; } visit[k] = 1; for (auto nk : m[k]) { if (deep < n - 1 && nk == e)continue; dfs(nk,deep+1); } RET: visit[k] = 0; h = h2; return false; } void hash(int k) { h = ((h * (k+123) + 666) * 789)%1000000007; } int n; int type; map<int, vector<int>> m;//邻接表 map<int, int>visit; map<long long, int>hashVisit; long long h = 1234567; int e; }; class Solution { public: int uniquePathsIII(vector<vector<int>>& grid) { row=grid.size(),col = grid[0].size(); int n = row*col; map<int, vector<int>>m; int s, e; for (int i = 0; i < row; i++)for (int j = 0; j < col; j++) { if (grid[i][j] == -1) { n--; continue; } if (grid[i][j] == 1)s = id(i, j); if (grid[i][j] == 2)e = id(i, j); vector<int> v = getNeighbor4(id(i, j)); for (int k : v)if(grid[k/col][k%col]!=-1)m[k].push_back(id(i, j)); } return Hamilton(n, m, 0,s,e).ans.size(); } int id(int x, int y) { return x * col + y; } vector<int> getNeighbor4(int k) { vector<int>ans; if (k >= col)ans.push_back(k - col); if (k < (row - 1) * col)ans.push_back(k + col); if (k % col)ans.push_back(k - 1); if (k % col < col - 1)ans.push_back(k + 1); return ans; } int row,col; };