搜索P1605迷宫

题目背景

迷宫 【问题描述】

给定一个N*M方格的迷宫&＃xff0c;迷宫里有T处障碍&＃xff0c;障碍处不可通过。给定起点坐标和

终点坐标&＃xff0c;问: 每个方格最多经过1次&＃xff0c;有多少种从起点坐标到终点坐标的方案。在迷宫

中移动有上下左右四种方式&＃xff0c;每次只能移动一个方格。数据保证起点上没有障碍。

输入样例 输出样例

【数据规模】

1≤N,M≤5

题目描述

输入输出格式

输入格式&＃xff1a;
【输入】

第一行N、M和T&＃xff0c;N为行&＃xff0c;M为列&＃xff0c;T为障碍总数。第二行起点坐标SX,SY&＃xff0c;终点

坐标FX,FY。接下来T行&＃xff0c;每行为障碍点的坐标。

输出格式&＃xff1a;
【输出】

给定起点坐标和终点坐标&＃xff0c;问每个方格最多经过1次&＃xff0c;从起点坐标到终点坐标的方

案总数。

AC代码1

首先判断下一步是否可以走&＃xff0c;可以走则进行递归&＃xff0c;并标记已选&＃xff08;即标记下一步&＃xff09;&＃xff0c;递归结束后还原标记。这个思路有坑的地方在于开始位置已经选择不可以再次递归&＃xff0c;但是一开始容易忽略。其次&＃xff0c;棋盘的定义也是花了我不少时间&＃xff0c;因为输入n*m是行和列&＃xff0c;所以行最小是1&＃xff0c;数组的最大值应为n&＃43;1&＃xff0c;对应的m也一样

#include
#includeusing namespace std;
int row1, row2, barrier;
int startx, starty, endx, endy;
int area[6][6] &＃61; {0};
int ans &＃61; 0;void dfs(int x &＃61; startx, int y &＃61; starty) {if (x &＃61;&＃61; endx && y &＃61;&＃61; endy) {ans&＃43;&＃43;;return;}//往上走 if (y < row2 && area[x][y &＃43; 1] !&＃61; 1) {area[x][y &＃43; 1] &＃61; 1;dfs(x, y &＃43; 1);area[x][y &＃43; 1] &＃61; 0;}//往下走 if (y > 1&& area[x][y - 1] !&＃61; 1) {area[x][y - 1] &＃61; 1;dfs(x, y - 1);area[x][y - 1] &＃61; 0;}//往右走if (x < row1&& area[x&＃43;1][y] !&＃61; 1) {area[x&＃43;1][y] &＃61; 1;dfs(x &＃43; 1, y);area[x&＃43;1][y] &＃61; 0;}//往左走if (x > 1 && area[x-1][y] !&＃61; 1) {area[x-1][y] &＃61; 1;dfs(x - 1, y);area[x-1][y] &＃61; 0;}
}
int main() {scanf("%d%d%d", &row1, &row2, &barrier);scanf("%d%d%d%d", &startx, &starty, &endx, &endy);while (barrier > 0) {int x, y;scanf("%d%d", &x, &y);area[x][y] &＃61; 1;barrier--;}area[startx][starty] &＃61; 1;dfs();printf("%d", ans);return 0;
}

优化

1 在四个方向上递归如果简单写的话&＃xff0c;可以利用int xs[4] &＃61; {-1, 1, 0, 0}; 的方式。可有可无
2 下面这种解法从当前位置开始标记&＃xff0c;结束条件是数组越界&＃xff08;索引大于行数和列数&＃xff09;或者访问到结束的结点

#include
#include
using namespace std;
int row1, row2, barrier;
int startx, starty, endx, endy;
int area[6][6] &＃61; {0};
int ans &＃61; 0;
int xs[4] &＃61; {-1, 1, 0, 0};
int ys[4] &＃61; {0, 0, -1, 1};
void dfs(int x &＃61; startx, int y &＃61; starty) {if (y < 1 || y > row2 || x < 1 || x > row1)return;if (x &＃61;&＃61; endx && y &＃61;&＃61; endy) {ans&＃43;&＃43;;return;}area[x][y] &＃61; 1;for (int i &＃61; 0; i < 4; &＃43;&＃43;i) {if (area[x &＃43; xs[i]][y &＃43; ys[i]] !&＃61; 1) {dfs(x&＃43;xs[i], y &＃43; ys[i]);}}area[x][y] &＃61; 0;
}
int main() {
// freopen("E:/下载/testdata (4).in","r",stdin);scanf("%d%d%d", &row1, &row2, &barrier);scanf("%d%d%d%d", &startx, &starty, &endx, &endy);while (barrier > 0) {int x, y;scanf("%d%d", &x, &y);area[x][y] &＃61; 1;barrier--;}dfs();printf("%d", ans);return 0;
}