洛谷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输入 #12 2 1 1 1 2 2 1 2输出 #11说明/提示对于100%100\%100%的数据1≤N,M≤51 \le N,M \le 51≤N,M≤51≤T≤101 \le T \le 101≤T≤101≤SX,FX≤N1 \le SX,FX \le N1≤SX,FX≤N1≤SY,FY≤M1 \le SY,FY \le M1≤SY,FY≤M。#includecstdiousingnamespacestd;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(xendXyendY){ans;return;}for(inti0;i4;i){intnxxdx[i];intnyydy[i];if(nx1nxnny1nym!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(inti0;it;i){inttmpx,tmpy;scanf(%d %d,tmpx,tmpy);vis[tmpx][tmpy]1;}dfs(startX,startY);printf(%d\n,ans);return0;}