洛谷P1605 迷宫

P1605 迷宫

题目描述

给定一个N×MN \times MN×M方格的迷宫，迷宫里有TTT处障碍，障碍处不可通过。

在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。

给定起点坐标和终点坐标，每个方格最多经过一次，问有多少种从起点坐标到终点坐标的方案。

输入格式

第一行为三个正整数N,M,TN,M,TN,M,T，分别表示迷宫的长宽和障碍总数。

第二行为四个正整数SX,SY,FX,FYSX,SY,FX,FYSX,SY,FX,FY。SX,SYSX,SYSX,SY代表起点坐标，FX,FYFX,FYFX,FY代表终点坐标。

接下来TTT行，每行两个正整数，表示障碍点的坐标。

输出格式

输出从起点坐标到终点坐标的方案总数。

输入输出样例 #1

输入 #1

2 2 1 1 1 2 2 1 2

输出 #1

1

说明/提示

对于100%100\%100%的数据，1≤N,M≤51 \le N,M \le 51≤N,M≤5，1≤T≤101 \le T \le 101≤T≤10，1≤SX,FX≤N1 \le SX,FX \le N1≤SX,FX≤N，1≤SY,FY≤M1 \le SY,FY \le M1≤SY,FY≤M。

#include<cstdio>usingnamespacestd;intn,m,t,startX,startY,endX,endY;intans;intdx[4]={0,0,1,-1};intdy[4]={1,-1,0,0};intvis[10][10];voiddfs(intx,inty){if(x==endX&&y==endY){ans++;return;}for(inti=0;i<4;++i){intnx=x+dx[i];intny=y+dy[i];if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&!vis[nx][ny]){vis[nx][ny]=1;dfs(nx,ny);vis[nx][ny]=0;}}}intmain(){scanf("%d %d %d",&n,&m,&t);scanf("%d %d %d %d",&startX,&startY,&endX,&endY);vis[startX][startY]=1;for(inti=0;i<t;++i){inttmpx,tmpy;scanf("%d %d",&tmpx,&tmpy);vis[tmpx][tmpy]=1;}dfs(startX,startY);printf("%d\n",ans);return0;}