int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 }; void dfs()//参数用来表示状态
{
if (到达终点状态)
{
...//根据题意来添加
return;
}
if (越界或者是不符合法状态)
return;
for (扩展方式)//一般是四个方向扩展
{
if (扩展方式所达到状态合法)
{
....//根据题意来添加
标记;
dfs();
修改(剪枝);
(还原标记);
//是否还原标记根据题意
//如果加上(还原标记)就是 回溯法
} }
}
洛谷P1605 迷宫:DFS
题目描述
迷宫 【问题描述】
给定一个N*M方格的迷宫,迷宫里有T处障碍,障碍处不可通过。给定起点坐标和终点坐标,
问: 每个方格最多经过1次,有多少种从起点坐标到终点坐标的方案。在迷宫
中移动有上下左右四种方式,每次只能移动一个方格。数据保证起点上没有障碍。
【数据规模】
1≤N,M≤5
输入输出格式
输入格式:
第一行N、M和T,N为行,M为列,T为障碍总数。第二行起点坐标SX,SY,终点
坐标FX,FY。接下来T行,每行为障碍点的坐标。
输出格式:
给定起点坐标和终点坐标,问每个方格最多经过1次,从起点坐标到终点坐标的方
案总数。
输入输出样例
输入样例#1:
2 2 1
1 1 2 2
1 2
输出样例#1:
1
#include<iostream>
#include<algorithm>
using namespace std; int a[8][8];//a数组记录地图障碍物
int book[8][8];//book数组标记走没走过,没走过的为0
int n, m,x,y, t, sx, sy, fx, fy,cnt=0;//cnt代表方案书
int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 }; bool check(int x, int y) {
return (a[x][y] != 1)&&(book[x][y]==0)&&x>0&&y>0&&x<=n&&y<=m;
} void dfs(int x,int y) {
if (x == fx&&y == fy) {
cnt++;
return;
}
for (int i = 0; i < 4; i++) {
int nx =x+ dx[i];
int ny =y+ dy[i];
if (check(nx, ny)) {
book[nx][ny] = 1;
dfs(nx, ny);
book[nx][ny] = 0;
}
}
return;
}
int main() {
cin >> n >> m >> t >> sx >> sy >> fx >> fy;
for (int i = 0; i < t; i++) {
cin >> x >> y;
a[x][y] = 1;
} book[sx][sy] = 1;//先把起点标记走过
dfs(sx, sy);
cout << cnt << "\n";
return 0;
}
//输入:
//00000
//11110
//00010
//00000
//00000
//输出:
//10