文章目录

• 前言
• 一、问题引出
• 二、问题解决
  • 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;
		}
	}
 	
}
}

总结

暂时就没有总结了。