蓝桥杯—数字接龙(dfs+减枝)

一.题目

二.思路

一看就是迷宫问题的变种，从左上角到达右下角，要解决

1.8个方向的方向向量，用dx，dy数组代表方向向量

2.要按照一个规律的数值串进行搜索0，1，2，k-1，0，1，2......，这个好实现只需要在dfs方法中加入一个下一个数值的参数搜索就行

3.核心减枝:斜对角线不能交叉(本题难点），这里用了一个四维数组来标记走过的对角线

(x,y)->(xx,yy)代表从对角线连线，mark[x][y][xx][yy]，mark数组只用于记录对角线连线

由下图可知：

在判断是否能进行对角线连线时只需要检测mark[x][b][a][y]即可

三.代码

public static int n;public static int[] dx = {-1,-1,0,1,1,1,0,-1};//八个方向的方向向量，注意要按照题目要求public static int[] dy = {0,1,1,1,0,-1,-1,-1};public static boolean[][] mark = new boolean[11][11];//判断数组public static boolean[][][][] mark1 = new boolean[12][12][12][12];//判断是否交叉public static int[] res = new int[100];//记录答案public static boolean t;//用于记录是否有路径可以到达右下角public static void main(String[] args) {Scanner scan = new Scanner(System.in);n = scan.nextInt();int k = scan.nextInt()-1;int[][] map = new int[n+1][n+1];for(int i = 1;i<=n;i++){for(int j = 1;j<=n;j++){map[i][j] = scan.nextInt();}}mark[1][1] = true;dfs(1,1,map,k,0,1);//数据范围很小dfs暴力搜索if(t==false) System.out.println(-1);scan.close();}public static void dfs(int x,int y,int[][] map,int k,int index,int cnt)//index走了几个格子,cnt下一步数值{if(t==true) return;if(index == n*n-1&&x==n&&y==n)//说明走完了，因为是按照字典顺序进行搜索的，所以第一个结果就是字典顺序最小的结果{t = true;for(int i = 0;i<n*n-1;i++){System.out.print(res[i]);}System.out.println();return;}for(int i = 0;i<8;i++){int xx = x + dx[i];int yy = y + dy[i];if(check(xx,yy,cnt,map))//说明没有走过,并且数值满足{if(i==1||i==3||i==5||i==7)//斜线走的(x,y)->(xx,yy){if(mark1[x][yy][xx][y]==true)continue;mark1[x][y][xx][yy] = true;mark1[xx][yy][x][y] = true;}mark[xx][yy] = true;res[index] = i;//记录结果int tmp = cnt;if(cnt==k)  cnt = 0;else cnt++;dfs(xx,yy,map,k,index+1,cnt);mark[xx][yy] = false;cnt = tmp;if(i==1||i==3||i==5||i==7) {//注意只有在i为奇数时才会操作对角线,这里的作用也是减枝mark1[x][y][xx][yy] = false;mark1[xx][yy][x][y] =false;}}}}public static boolean check(int x,int y,int cnt,int[][] map)//减枝{if(x>=1&&x<=n&&y>=1&&y<=n&&mark[x][y]==false)//根据题意出现交叉的无所谓不用处理{if(map[x][y]==cnt) return true;}return false;}