题目背景
迷宫 【问题描述】
给定一个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<cstdio>
- #include<cstring>
- #include<iostream>
- #include<algorithm>
- using
- namespace
- std
- ;
- int
- n
- ,
- t
- ,
- m
- ,
- ans
- ;
- int
- dx
- [
- 4
- ]={
- 0
- ,
- 0
- ,-
- 1
- ,
- 1
- };
- int
- dy
- [
- 4
- ]={-
- 1
- ,
- 1
- ,
- 0
- ,
- 0
- };
- int
- map
- [
- 6
- ][
- 6
- ];
- int capsule,expertise,tablet,sideways;
- void
- dfs
- (
- int
- x
- ,
- int
- y
- ){
- if(x==tablet&&y==sideways){
- ans++;
- return
- ;
- }
- for
- (
- int
- i
- =
- 0
- ;
- i
- <
- 4
- ;
- i
- ++){
- int
- cx
- =
- x
- +
- dx
- [
- i
- ];
- int
- cy
- =
- y
- +
- dy
- [
- i
- ];
- if(!map[cx][cy]&&cx>=1&&cx<=n&&cy>=1&&cy<=m){
- map
- [
- cx
- ][
- cy
- ]=
- 1
- ;
- dfs
- (
- cx
- ,
- cy
- );
- map
- [
- cx
- ][
- cy
- ]=
- 0
- ;
- }
- }
- }
- int main(){
- scanf("%d%d%d",&n,&m,&t);
- scanf("%d%d%d%d",&capsule,&expertise,&tablet,&sideways);
- for
- (
- int
- i
- =
- 1
- ;
- i
- <=
- t
- ;
- i
- ++){
- int
- x
- ,
- y
- ;
- scanf("%d%d",&x,&y);
- map
- [
- x
- ][
- y
- ]=
- 1
- ;
- }
- map[capsule][expertise]=1;
- dfs
- (
- capsule
- ,
- expertise
- );
- cout
- <<
- ans
- ;
- }