蓝桥杯国赛—1022玩具蛇

目录

一.题目

二.分析题意

三.代码

一.题目

二.分析题意

本题为一道程序填空题，要求我们将一个4*4的盒子填满，实际上就是遍历一个4*4的矩阵的所有可能路径这道题用bfs和dfs都可以，博主这里用的是dfs，用dfs找所有可能路径就需要在递归里进行回溯

三.代码

public class text4 {

public static long sum = 0;

public static void main(String[] args) {

Scanner scan = new Scanner(System.in);

int n = 4;

boolean[][] mark = new boolean[4][4];

for(int i = 0;i<n;i++)

{

for(int j = 0;j<n;j++)

{

dfs(i,j,mark,0);

}

}

System.out.println(sum);

scan.close();

}

public static void dfs(int x,int y,boolean[][] mark,int index)

{

if(!(x>=0&&x<4&&y>=0&&y<4&&mark[x][y]==false))

return;

if(index >= 15) {

sum++;

return;

}

mark[x][y] = true;

dfs(x+1,y,mark,index+1);

dfs(x-1,y,mark,index+1);

dfs(x,y+1,mark,index+1);

dfs(x,y-1,mark,index+1);

mark[x][y] = false;

}

}

java

四.第一次做时错误原因

一开始将减枝语句放在了sum++后面，导致将不符合条件的路径也计算了进去