洛谷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

AC代碼

注意要對起點也進行標記，否則只能拿到70分
不對起點進行標記的被卡的數據：

2 2 0
1 1 1 2

#include<bits/stdc++.h>
#define ll long long
#define ms(a,b) memset(a,b,sizeof(a))
#define INF 0x7f7f7f7f
const int maxn=1e6+10;
using namespace std;
int mp[10][10];
int vis[100][100];
int dis[4][2]={1,0,-1,0,0,1,0,-1};
int n,m,t;
int ans;
void dfs(int x,int y,int fx,int fy)
{vis[x][y]=1;if(x==fx&&y==fy)ans++;for(int i=0;i<4;i++){int dx=x+dis[i][0];int dy=y+dis[i][1];if(!vis[dx][dy]&&!mp[dx][dy]&&dx<=n&&dx>0&&dy<=m&&dy>0){dfs(dx,dy,fx,fy);vis[dx][dy]=0;}}
}
int main()
{ios::sync_with_stdio(false);cin>>n>>m>>t;int sx,sy,fx,fy;cin>>sx>>sy>>fx>>fy;int zx,zy;for(int i=0;i<t;i++){cin>>zx>>zy;mp[zx][zy]=1;}dfs(sx,sy,fx,fy);cout<<ans<<endl;return 0;
}