dfs判断连通性的问题
先用dfs递归出所有的排列，在判断连通性，符合条件的答案加一 ；
因为全排列考虑了顺序问题，但是所以有5！中重复的情况 即/120 即可；
小技巧：因为避免出现边界的处理问题 把差为1却不在同一行的数删去，这样能更轻松的处理边界问题
连通性的判断：对每一个点进行遍历，向四个方向遍历，找到连通点就继续dfs，找不到直接退回来，直到找到这五个点都连通就返回符合条件，答案加一
#include<iostream> #include<algorithm> #include<cstring> using namespace std ; int v[500]; int a[12] = {1,2,3,4,6,7,8,9,11,12,13,14} ; int ans ; int flag1 , flag2 ; int path[5]; int d[4] = {-1,1,-5,5} ; int state[5] ;//暂存当前这个路径的点是否遍历过 void dfs2(int u){//第二个dfs负责判断连通性 for(int i = 0 ; i < 4 ; i++){//遍历四个方向 int t = path[u] + d[i] ; if(t <1 || t >14 || t ==5 || t==10) continue ;//判断边界条件 for(int j = 0 ; j <5 ; j ++){//遍历每一个点，是否和当前这个点连通 if(!state[j] && path[j] == t){ state[j] = 1 ; dfs2(j) ; } } } } void dfs1(int u){//第一个dfs用来找全排列，和判断是否符合条件 if(u == 5){ flag2 = 1 ; memset(state,0,sizeof(state)) ;//用到好几次，所以每一次都要遍历 // for(int i = 0 ; i < 5 ; i ++) state[i] = 0 ; state[0] = 1 ;//第一个进去的点一定遍历过了 dfs2(0) ; // int p ; // for(p = 0 ; p < 5 ; p ++){ // if(!state[p]) break ; // } // if(p == 5) ans ++ ; for(int i = 0 ; i < 5 ; i ++) if(state[i] ==0 ) flag2 = 0 ; if(flag2) ans ++ ; return ; } for(int i = 0 ; i < 12 ; i ++){//找全排列 if(!v[i]){ v[i] = 1 ; path[u] = a[i] ; dfs1(u+1) ; v[i] = 0 ; } } } int main(){ dfs1(0) ; cout << ans/120 << endl ; return 0 ; }
