题意：
手机九宫格锁，共9个数，然后给出规定，只能用给定的n个数做密码，求不同的锁屏方法有几种
对于一个点可以走向其他相邻8个方向，对于中间有相互隔开的情况，例如1到3，如果2已经访问过，那么方案是可行的，输出所有锁屏方案路径要点：
可以DFS或直接排列判断，排列的话主要的难点在于判断是否合法，因为数据较小，直接打表出要考虑的几种情况，并用一个vis数组对每一个排列从头到尾进行是否走过的记录。我反正是想不出来，看了别人的代码感觉还算简单，还是太弱鸡了。
打表+枚举：
#include#include #include #include using namespace std;int mp[15][15],a[15];int vis[15];int result[400000][15];int n;void init() //打表，不能通过的顺序{ mp[1][3] = 2; mp[3][1] = 2; mp[1][7] = 4; mp[7][1] = 4; mp[1][9] = 5; mp[9][1] = 5; mp[2][8] = 5; mp[8][2] = 5; mp[3][7] = 5; mp[7][3] = 5; mp[3][9] = 6; mp[9][3] = 6; mp[4][6] = 5; mp[6][4] = 5; mp[7][9] = 8; mp[9][7] = 8;}bool check() //按照当前排列顺序走能否成功{ vis[a[0]] = 1; //记录是否走过 for (int i = 1; i < n; i++) { int v = mp[a[i - 1]][a[i]];//当前连续的两个中间的值，看是否需要跳过 if (!(!v || vis[v]) && (!vis[a[i]]))//成功的条件：不用考虑跳过或要跳过的已经走过并且当前还没走过 return false; //整个取反输出失败 vis[a[i]] = 1; //当前的已经走过 } return true;}int main(){ int t,i,j; scanf("%d", &t); while (t--) { memset(mp, 0, sizeof(mp)); init(); scanf("%d", &n); for (i = 0; i < n; i++) scanf("%d", &a[i]); sort(a, a + n); //因为要按字典序输出，所以先排序 int num = 0; do { memset(vis, 0, sizeof(vis)); if (check()) { num++; memcpy(result[num], a, sizeof(a)); } } while (next_permutation(a, a + n));//直接下一个排列 printf("%d\n", num); for (i = 1; i <= num; i++) { for (j = 0; j < n - 1; j++) printf("%d ", result[i][j]); printf("%d\n", result[i][n-1]); } } return 0;}
DFS：
对于每一个点都可以往剩下的8个点走。重点就是不断两个两个比较，然后传递第二个作为下一次的第一个
#include#include #include #include using namespace std;int vis[300],a[11],mp[11][11];int ans[400000][11],f[11];int n,len;void init(){ mp[1][3] = 2; mp[3][1] = 2; mp[1][7] = 4; mp[7][1] = 4; mp[1][9] = 5; mp[9][1] = 5; mp[2][8] = 5; mp[8][2] = 5; mp[3][7] = 5; mp[7][3] = 5; mp[3][9] = 6; mp[9][3] = 6; mp[4][6] = 5; mp[6][4] = 5; mp[7][9] = 8; mp[9][7] = 8;}void print(){ for (int i = 0; i < n; i++) { ans[len][i] = f[i]; } len++;}void dfs(int cur,int x){ if (x == n) { print(); return; } for (int i = 0; i