迷宫
题目链接
这道题就是一道简单的dfs计方案数qwq。
我的思路是把表初始化为1，再将障碍改为0，因为在全局定义中数组会直接初始化为0，所以就少去了对边界的特判。
- next数组加循环可以减少代码量。
- 注意一定要记得先把起始点标记！！！
AC代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 2000
using namespace std;
int N,M,T;
int SX,SY,FX,FY;
int total;
int G[MAXN][MAXN];
int vis[MAXN][MAXN];
void dfs(int x,int y,int step)
{
int next[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int a,b;
if(x==FX&&y==FY)
{
total++;
return;
}
for(int i=0;i<=3;i++)
{
a=x+next[i][0];
b=y+next[i][1];
if(G[a][b]==1&&vis[a][b]==0)
{
vis[a][b]=1;
dfs(a,b,step+1);
vis[a][b]=0;
}
}
return;
}
int main()
{
scanf("%d%d%d",&N,&M,&T);
scanf("%d%d%d%d",&SX,&SY,&FX,&FY);
for(int i=1;i<=N;i++)
{
for(int j=1;j<=M;j++)
{
G[i][j]=1;
}
}
for(int i=1;i<=T;i++)
{
int x,y;
scanf("%d%d",&x,&y);
G[x][y]=0;
}
vis[SX][SY]=1;
dfs(SX,SY,0);
printf("%d",total);
return 0;
}