题目链接:P1605 迷宫 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目描述
给定一个 N×M 方格的迷宫,迷宫里有 T 处障碍,障碍处不可通过。
在迷宫中移动有上下左右四种方式,每次只能移动一个方格。数据保证起点上没有障碍。
给定起点坐标和终点坐标,每个方格最多经过一次,问有多少种从起点坐标到终点坐标的方案。
输入格式
第一行为三个正整数 N,M,T,分别表示迷宫的长宽和障碍总数。
第二行为四个正整数 SX,SY,FX,FY,其中,SX,SY 代表起点坐标,FX,FY 代表终点坐标。
接下来 T 行,每行两个正整数,表示障碍点的坐标。
输出格式
输出从起点坐标到终点坐标的方案总数。
样例 #1
样例输入 #1
2 2 1
1 1 2 2
1 2
样例输出 #1
1
提示
对于 100% 的数据,1 <= N,M <= 5,1 <= T <= 10,1 <= SX,FX <= n,1 <= SY,FY <= m。
AC code:(DFS)
#include<iostream>
#include<algorithm>
using namespace std;
/*
0 0 0 0 0 0
0 1 1 1 1 0
0 1 2 2 1 0
0 1 2 * 1 0
0 1 1 1 1 0
0 0 0 0 0 0
*/
int dir[4][2]={{0,1}, // 右
{1,0}, // 下
{0,-1},// 左
{-1,0}};// 上
int a[10][10],book[10][10];
int startx,starty,endx,endy;
int cnt;
void dfs(int x,int y,int step)
{
if(x==endx && y==endy)
{
cnt++;
return ;
}
for(int i=0;i<4;i++)
{
int tx=x+dir[i][0];
int ty=y+dir[i][1];
if(a[tx][ty]==1 && book[tx][ty]==0)
{
book[tx][ty]=1;
dfs(tx,ty,step+1);
book[tx][ty]=0;
}
}
return ;
}
int main()
{
int n,m,t;
cin>>n>>m>>t;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
a[i][j]=1;
cin>>startx>>starty>>endx>>endy;
while(t--)
{
int i,j;
cin>>i>>j;
a[i][j]=2;
}
book[startx][starty]=1;
dfs(startx,starty,0);
cout<<cnt<<endl;
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)