目录
一.题目
二.分析题意
三.代码
一.题目
二.分析题意
本题为一道程序填空题，要求我们将一个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++后面，导致将不符合条件的路径也计算了进去
