19712 数字接龙

/*我觉得重要的理解点：1.四维数组白表示一个点从另一个点沿对角线的方式进行移动，如果这个元素的值为真则表示这样的移动存在。 2.按照0->k-1的顺序移动。这个要求的实现方法也值得学习 3.count和index的含义： index表示索引，表示第index步。当index=0表示在起点，ndex=1表示从原点出发走了一步。count表示走过的格子数。count=n*n表示所有的格子都已经走过。
*/ 

#include<bits/stdc++.h>
using namespace std;
int n, k, fx[8][2] = {{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}}; // 2列8行的数组，按照行初始化
//从向左移动开始。顺时针的移动顺序
//即正左，左上，正上，右上，正右，右下，正下，左下
int maps[11][11]; // 存储地图信息的二维数组
bool vis[11][11], b = false, check[11][11][11][11]; // 访问标记，结束标记，交叉检查
vector<int> v; // 存储路径
//四维数组check[a][b][c][d]表示从(a,b)->(c,d)其中此两点为对角线关系，
//即check[a][b][c][d]表示(a,b)通过斜线访问到(c,d);
//同样的check[c][d][a][b]表示从(c,d)->(a,b)// 深度优先搜索函数
void dfs(int x, int y, int index, int count) {if (b) return; // 剪枝，如果已经找到答案则不再继续搜索if (x == n && y == n && count == n * n) { // 判断是否到达终点//count表示走过的格子总数b = true;for (int i = 0; i < v.size(); i++) cout << v[i]; // 输出路径return;for (int i = 0; i < 8; i++) { // 遍历所有可能的移动方向int xx = x + fx[i][0], yy = y + fx[i][1]; // 新坐标if (xx < 1 || yy < 1 || xx > n || yy > n || vis[xx][yy]) continue; // 判断移动是否合法if (maps[xx][yy] != (index + 1) % k) continue; //index"索引". index=0表示在当前位置//index+1 表示下一个步骤的位置//maps[x][y]+1=maps[xx][yy]//[x][y]时index=index；//[xx][yy]index=index+1;//%k使得能够循环判断。将值控制在0->k-1的范围之内。//判断是否按照0~k-1的顺序走.if (i % 2 && check[x + fx[i][0]][y][x][y + fx[i][1]] || check[x][y + fx[i][1]][x + fx[i][0]][y]) continue; // 交叉检查//if触发条件：对角线移动且存在交叉//示意图：  a b//         c d//判断交叉的原理：假设从c(x,y)点出发，当i=3时表示向右上移动到b；//此时check[x + fx[i][0]][y][x][y + fx[i][1]]为check[x+1][y][x][y+1]//即a->d是否为1//同时判断check[x + fx[i][0]][y][x][y + fx[i][1]] (check[x][y+1][x+1][y])//即d->a是否为1//有一个为1则为交叉vis[xx][yy] = true; // 标记为已访问if (i % 2) {check[x][y][xx][yy] = true; check[xx][yy][x][y] = true;} // 标记交叉点v.push_back(i); // 答案的写入dfs(xx, yy, (index + 1) % k, count + 1); // 递归vis[xx][yy] = false; // 回溯//回溯的原因//1.没有按照规定的顺序走 0->k-1//2.存在交叉//3.越界或者到终点//回溯之后说明这个点非法，则将标记清除，不影响其他路径规划。if (i % 2) {check[x][y][xx][yy] = false; check[xx][yy][x][y] = false;} // 回溯交叉点v.pop_back(); }
}int main() {cin >> n >> k; // 输入网格大小和要求for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {cin >> maps[i][j]; // 输入网格信息}}vis[1][1] = true; // 从(1,1)开始dfs(1, 1, 0, 1); // 深度优先搜索if (!b) cout << -1; // 如果没有找到答案，输出-1return 0;
}

无向图存在欧拉回路（回到原点）的充要条件：每个点的度数为偶数

度数：连接一个点的条数。 为奇数的点为奇点，偶数为偶点。

不闭合的欧拉路径存在的充要条件：奇顶点的个数等于0或2；

定理2：一个无向图有2n个奇顶点，最少需要n笔画成；

一个图是否能够不重复的遍历所有顶点：能则为哈密顿图

哈密顿图:遍历所有顶点

欧拉：遍历所有边