三、迷宫

题目描述

给定一个 N×M 方格的迷宫，迷宫里有 T 处障碍，障碍处不可通过。

在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。

给定起点坐标和终点坐标，每个方格最多经过一次，问有多少种从起点坐标到终点坐标的方案。

输入格式

第一行为三个正整数 N,M,T，分别表示迷宫的长宽和障碍总数。

第二行为四个正整数 SX,SY,FX,FY，SX,SY 代表起点坐标，FX,FY 代表终点坐 标。

接下来 T 行，每行两个正整数，表示障碍点的坐标。

输出格式

输出从起点坐标到终点坐标的方案总数。 输入输出样例

输入

2 2 1
1 1 2 2
1 2

输出

1

说明/提示

对于 100% 的数据， 1≤N,M≤5， 1≤T≤10， 1≤SX,FX≤n，1≤ , ≤ 。

视频题解

https://dl.ccf.org.cn/video/videoDetail.html?_ack=1&id=7092424600864768

AC代码

#include <iostream>
using namespace std;
int n,m,t,sx,sy,fx,fy,ans = 0 ;
int maze[11][11],used[11][11]; // 初始化为0
int FX[4][2] = {  // 上、右、下、左（顺时间 偏移量 x,y ）
	{-1,0},	//上移 ：行-1，列不变
	{0,1},  //右移 : 行不变，列+1
	{1,0},  //下移 : 行-1，列不变
	{0,-1}  //左移 : 行不变，列-1
}; 
void dfs(int x,int y){
	if(x == fx && y == fy){// 到达终点
		ans ++;
		return;
	}
	used[x][y] = 1;
	for(int i = 0 ; i <4; i++){
		// 4个方向移动后
		int nx = x + FX[i][0];
		int ny = y + FX[i][1];
		if( (nx >= 1&& nx <= n) && (y >= 1 && y <= m)  &&
			used[nx][ny] == 0 && maze[nx][ny] == 0){	   // 不是障碍物且没有走过
				used[nx][ny] = 1;//标记为走过
				dfs(nx,ny);
				// 回溯
				used[nx][ny] = 0;
			}	
		
	}
}
int main() {
	cin >> n >> m >> t;
	cin >> sx >> sy >> fx >> fy; // 起点坐标和终点坐标
	// 障碍物
	int x,y;
	for(int i=1; i<= t;i++){
		cin >> x >> y;
		maze[x][y] = 1 ;// 标记为1，表示有障碍物
	}
	dfs(sx,sy); // 深度搜索
	cout << ans;
	return 0;
}