题目背景
迷宫 【问题描述】
给定一个N*M方格的迷宫，迷宫里有T处障碍，障碍处不可通过。给定起点坐标和
终点坐标，问: 每个方格最多经过1次，有多少种从起点坐标到终点坐标的方案。在迷宫
中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。
输入样例 输出样例
【数据规模】
1≤N,M≤5
题目描述
输入输出格式
输入格式：
【输入】
第一行N、M和T，N为行，M为列，T为障碍总数。第二行起点坐标SX,SY，终点
坐标FX,FY。接下来T行，每行为障碍点的坐标。
输出格式：
【输出】
给定起点坐标和终点坐标，问每个方格最多经过1次，从起点坐标到终点坐标的方
案总数。
输入输出样例
题意：
在一个n*m的格子中，有t个障碍物。
问从给定的起点走到给定的终点，每个格子只经过一次的走法有多少种。
思路：
dfs，走到终点方案数++
要注意，dfs之前要先把起点的vis标记为已访问。因为这个WA了一发。
//#include<bits/stdc++>
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stdlib.h>
#include<queue>
#include<map>
#include<stack>
#include<set> #define LL long long
#define ull unsigned long long
#define inf 0x3f3f3f3f using namespace std; int n, m, t;
bool barrier[][];
bool vis[][];
int stx, sty, edx, edy;
int dx[] = {, , -, };
int dy[] = {, -, , };
int ans = ; bool check(int x, int y)
{
return(x > && y > && x <= n && y <= m && !barrier[x][y] && !vis[x][y]);
} void dfs(int x, int y)
{
if(x == edx && y == edy){
ans++;
return;
}
int cnt = ;
for(int i = ; i < ; i++){
if(check(x + dx[i], y + dy[i])){
vis[x + dx[i]][y + dy[i]] = true;
dfs(x + dx[i], y + dy[i]);
vis[x + dx[i]][y + dy[i]] = false;
}
}
return;
} int main()
{
scanf("%d%d%d", &n, &m, &t);
scanf("%d%d", &stx, &sty);
scanf("%d%d", &edx, &edy);
for(int i = ; i < t; i++){
int x, y;
scanf("%d%d", &x, &y);
barrier[x][y] = true;
}
vis[stx][sty] = true;
dfs(stx, sty);
printf("%d\n", ans); return ;
}