package _5_23;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.Stack;
public class _16y05 {
static int[][] pos = {{-1,0},{1,0},{0,-1},{0,1}};
static int b[][] = new int[100][100];
static int c[][] = new int[100][100];
static int n,m,t;
static int bx,by,ex,ey;
static int tx,ty;
static int min_count = 0;
static String s ="";
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
t = sc.nextInt();
bx = sc.nextInt()-1;
by = sc.nextInt()-1;
ex = sc.nextInt()-1;
ey = sc.nextInt()-1;
for(int i = 0;i<t;i++) {
int tx1 = sc.nextInt();
int ty1 = sc.nextInt();
//System.out.println(tx1+" "+ty1);
b[tx1-1][ty1-1] = 1;
}
/*for(int i=0;i<n;i++) {
for(int j =0;j<m;j++) {
System.out.print(b[i][j]+" ");
}
System.out.println();
}*/
c[bx][by] = 1;
dfs(bx,by);
System.out.println(min_count);
}
private static void dfs(int x, int y) {
// TODO Auto-generated method stub
if((x==ex)&&(y==ey)) {
min_count++;
return;
}
for(int i=0;i<4;i++) {
int x1 =x +pos[i][0];
int y1 = y +pos[i][1];
if(x1>=0&&y1>=0&&x1<n&&y1<m&&(b[x1][y1]==0)&&(c[x1][y1]==0)) {
c[x1][y1] = 1;
dfs(x1,y1);
c[x1][y1] = 0;
}
}
}
}
求最短路径
package com.bean.algorithmbasic;
public class DFSMaze {
/**
* DFS算法解决走迷宫问题
* 0: 表示通路
* 1: 表示死路
*
*/
static String path = "";
static String shortestPath = "";
public static void dfsMaze(int x, int y, int[][] maze) {
/*
* 获得矩阵的大小
* */
int m=maze.length;
int n=maze[0].length;
//设置结束条件
if (x < 0 || y < 0)
return;
// 如果坐标越界，或者 maze[x][y]==1 表示遇到障碍
if (x > m - 1 || y > n - 1 || maze[x][y] ==1)
return;
//表示遇到障碍
if (maze[x][y] == 1)
return; // 判断是否通路和越界
if (x == m - 1 && y == n - 1) { // 判断是否抵达出口
path = path + "(" + x + "," + y + ")";
if (shortestPath.length() == 0 || shortestPath.length() > shortestPath.length())
shortestPath = path;
System.out.println("找到路线:" + path);
return;
}
String temp = path;
path = path + "(" + x + "," + y + ")" + "-"; // 记录路线
maze[x][y] = 1; // 将走过的路标记
// 向四个方向搜索
dfsMaze(x + 1, y, maze); //向右搜索
dfsMaze(x, y + 1, maze); //向下搜索
dfsMaze(x, y - 1, maze); //向上搜索
dfsMaze(x - 1, y, maze); //向左搜索
// 将路线和标记恢复成上一次的状态
maze[x][y] = 0;
//清除
path = temp;
}
public static void main(String[] args) {
// 初始化一个迷宫地图
// 0: 表示通路
// 1:表示死路
int[][] maze = {
{0, 0, 1, 1, 1, 1, 1, 1, 1},
{1, 0, 0, 0, 0, 0, 0, 0, 1},
{1, 0, 1, 1, 0, 1, 1, 0, 1},
{1, 0, 1, 0, 0, 1, 0, 0, 1},
{1, 0, 1, 0, 1, 0, 1, 0, 1},
{1, 0, 0, 0, 0, 0, 1, 0, 1},
{1, 1, 0, 1, 1, 0, 1, 1, 1},
{1, 0, 0, 0, 0, 0, 0, 0, 0},
{1, 1, 1, 1, 1, 1, 1, 1, 0}
};
/*
* 从矩阵的左上角位置开始搜索
* */
dfsMaze(0, 0, maze);
if (shortestPath.length() != 0)
System.out.println("最短路线为：" + shortestPath);
else
System.out.println("没有找到路线！");
}
}
