洛谷P1605 迷宫【dfs】
题目背景
迷宫 【问题描述】
给定一个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了一发。
1 //#include<bits/stdc++> 2 #include<stdio.h> 3 #include<iostream> 4 #include<algorithm> 5 #include<cstring> 6 #include<stdlib.h> 7 #include<queue> 8 #include<map> 9 #include<stack> 10 #include<set> 11 12 #define LL long long 13 #define ull unsigned long long 14 #define inf 0x3f3f3f3f 15 16 using namespace std; 17 18 int n, m, t; 19 bool barrier[10][10]; 20 bool vis[10][10]; 21 int stx, sty, edx, edy; 22 int dx[4] = {0, 0, -1, 1}; 23 int dy[4] = {1, -1, 0, 0}; 24 int ans = 0; 25 26 bool check(int x, int y) 27 { 28 return(x > 0 && y > 0 && x <= n && y <= m && !barrier[x][y] && !vis[x][y]); 29 } 30 31 void dfs(int x, int y) 32 { 33 if(x == edx && y == edy){ 34 ans++; 35 return; 36 } 37 int cnt = 0; 38 for(int i = 0; i < 4; i++){ 39 if(check(x + dx[i], y + dy[i])){ 40 vis[x + dx[i]][y + dy[i]] = true; 41 dfs(x + dx[i], y + dy[i]); 42 vis[x + dx[i]][y + dy[i]] = false; 43 } 44 } 45 return; 46 } 47 48 int main() 49 { 50 scanf("%d%d%d", &n, &m, &t); 51 scanf("%d%d", &stx, &sty); 52 scanf("%d%d", &edx, &edy); 53 for(int i = 0; i < t; i++){ 54 int x, y; 55 scanf("%d%d", &x, &y); 56 barrier[x][y] = true; 57 } 58 vis[stx][sty] = true; 59 dfs(stx, sty); 60 printf("%d ", ans); 61 62 return 0; 63 }