文章目录
- 前言
- 一、问题引出
- 二、问题解决
- 1.思路分析
- 2.代码实现
- 总结
提示:以下是本篇文章正文内容,下面案例可供参考
一、迷宫问题
1.题目背景
给定一个N*M方格的迷宫,迷宫里有T处障碍,障碍处不可通过。给定起点坐标和终点坐标,问: 每个方格最多经过1次,有多少种从起点坐标到终点坐标的方案。在迷宫中移动有上下左右四种方式,每次只能移动一个方格。数据保证起点上没有障碍。
2.输入格式
第一行N、M和T,N为行,M为列,T为障碍总数。第二行起点坐标SX,SY,终点坐标FX,FY。接下来T行,每行为障碍点的坐标。
3.输出格式
给定起点坐标和终点坐标,问每个方格最多经过1次,从起点坐标到终点坐标的方案总数。
二、问题解决
1.分析问题
首先认识到这个题是一个经典的深度优先搜索(DFS)问题。
深度优先搜索。
顾名思义,和二叉树的深度优先搜索(下面用DFS来代替)相同。
DFS的标准格式
void dfs(int start,int ing)
{
停止条件。(经常用if 来判断 然后 return返回)
判断条件。
递归事件。}
解决思路:
1.创建迷宫。
2.设置障碍。
3.设置终起点。
4.利用DFS进行搜索。
四个方向进行探索。
探索方式。
利用数组进行。 比如 int xx[]={-1,0,1,0} int yy[]={0,1,0-1};
这里的模拟细究
比如 当前 伸出 x=3 y=3 的位置 如果向上探索 x-1 y 不变 向右 那便是 x 不变 y+1 所以 以此类推
上右下左 然后 顺序为 以此为 x-1 y+1 x+1 y-1 则 这也是 xx数组 和yy数组的赋值原因。
然后判断条件。
如下:
2.代码实现
代码如下(示例):
import java.util.Scanner;
public class 搜索 {
private static int[] arr=new int[40];//为每一列
private static int[] v=new int[40];//从左上到右下
private static int[] r=new int[40];//从右上到左下
private static int n;
private static int index;
private static int[] a=new int[20];
public static void main(String[] args) {
// TODO 自动生成的方法存根
Scanner in =new Scanner(System.in);
n=in.nextInt();
f2(1);
System.out.println(index);
}
static void f2(int x)
{
if(x>n)
{
index++;
if(index<=3)
{
for(int i=1;i<=n;i++)
{
System.out.print(a[i]+" ");
}
System.out.println();
}
return;
}
for(int i=1;i<=n;i++)
{
if(arr[i]!=1&&v[x-i+n]!=1&&r[x+i]!=1)
{
arr[i]=1;
v[x-i+n]=1;
r[x+i]=1;
a[x]=i;
f2(x+1);
arr[i]=0;
v[x-i+n]=0;
r[x+i]=0;
}
}
}
}
总结
暂时就没有总结了。