19712数字接龙

数字接龙

思路：

1. dfs

2. nxt[i][j]={-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}

3. 判断下一步是否可以走：
   0°没有走过
   1°不越界
   2°是前一个数字(x+1)%K
   3°字典序
   4°不交叉
   只用判断斜着走可能出现交叉
   (-1,1)->判断(-1,0)和(0,1)是不是都走过
   (1,1)->判断(1,0)和(0,1)是不是都走过
   (1,-1)->判断(1,0)和(0,-1)是不是都走过
   (-1,-1)->判断(-1,0)和(0,-1)是不是都走过
   最后要检查，是不是所有格子都经过了一次

4. (实际上，上述不交叉的判断有漏洞，是过分的剪枝，会去除一些可能正确的答案)

   比如：

   a[x][y]想走到a[x-1][y+1]，即使a[x-1][y]和a[x][y+1]都走过，也并不意味着两点之间直接相连(绕路)

   所以需要一个step[i][j]，如果abs(step[x-1][y]-a[x][y+1])==1，则这两点直连

图解：

代码：

int n,k,sx,sy,ex,ey;//startx,starty,endx,endy
int e[N][N],book[N][N],step[N][N],nxt[8][2]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};void dfs(string cs,int x,int y)//cs:current-string (x,y)当前所在坐标
{int tx,ty;char ch;int num=e[x][y];//当前位置的数字 if(x==ex&&y==ey){for(int i=0;i<n;++i){for(int j=0;j<n;++j){if(book[i][j]==0) return ;//没有经过所有格子-非法 }}cout<<cs;exit(0);}for(int i=0;i<8;++i){//遍历八个方向tx=x+nxt[i][0];ty=y+nxt[i][1];if(tx<0||ty<0||tx>=n||ty>=n) continue;//超界if(book[tx][ty]==0&&e[tx][ty]==(num+1)%k){//没访问 序列的数字连续0,1,2,...,k-1if(i%2==1){//东北 东南 西南 西北if(book[tx][y]==1&&book[x][ty]==1&&abs(step[tx][y]-step[x][ty])==1) continue;step[tx][ty]=step[x][y]+1;book[tx][ty]=1;ch=i+'0';dfs(cs+ch,tx,ty);step[tx][ty]=0;book[tx][ty]=0;				}else{//上 右 下 左step[tx][ty]=step[x][y]+1;book[tx][ty]=1;ch=i+'0';dfs(cs+ch,tx,ty);step[tx][ty]=0;book[tx][ty]=0;}}}
}int main()
{cin>>n>>k;sx=0,sy=0,ex=n-1,ey=n-1;for(int i=0;i<n;++i){for(int j=0;j<n;++j){cin>>e[i][j];}}book[sx][sy]=1;step[sx][sy]=0;if(e[sx][sy]!=0){//特判起点数字如果不是0-非法cout<<-1;return 0;}dfs("",sx,sy);cout<<-1;return 0;
}