(Luogu) p1605 maze (once you enter the deep search, it's like a sea of bitterness, and from then on, it's a big die)

Background

Given a N*M The maze of squares , There is... In the maze T Obstacles , A barrier is not accessible . Given the coordinates of the starting point and the ending point , ask : Each square goes through at most 1 Time , How many schemes are there from the starting point coordinate to the ending point coordinate . There are four ways to move in the maze , Only one square can be moved at a time . The data ensures that there are no obstacles at the starting point .

Title Description

nothing

Input format

first line N、M and T,N For the line ,M Column ,T For the total number of obstacles . The second line starts at SX,SY, End coordinates FX,FY. Next T That's ok , Coordinates of each obstacle point .

Output format

Given the coordinates of the starting point and the ending point , Ask each square to go through at most 1 Time , The total number of schemes from the start coordinate to the end coordinate .

I/o sample

Input #1

2 2 1
1 1 2 2
1 2

Output #1

1

explain / Tips

【 Data scale 】

1≤N,M≤5

This is a classic. You can't search deeply in the classic , To tell the truth, just set a formula to search , Anyway, time will not exceed .

Friends who don't know deep search can go bibi On , See the Getting Started Guide .（ Of course, you are also welcome to communicate with me ）

（ Recently, bloggers are busy playing games , Do the title , Study things , Has been ge, I'm sorry ）

#include <iostream>

using namespace std;
int N,M,T;
int sx,sy,fx,fy;
int maze[6][6];
bool vis[6][6];
int sum=0;
int dir[4][2]={
   {-1,0},{0,-1},{1,0},{0,1}};
bool in(int x,int y)
{
    return x>=1&&x<=N&&y>=1&&y<=M;
}
void dfs(int x,int y)
{
    if(x==fx&&y==fy)
    {
        sum++;
    }
    vis[x][y]=1;
    for(int i=0;i<4;i++)
    {
        int tx=x+dir[i][0];
        int ty=y+dir[i][1];
        if(in(tx,ty)&&maze[tx][ty]!=1&&!vis[tx][ty])
        {
            dfs(tx,ty);
        }
    }
    vis[x][y]=0;
}
int main()
{
    cin>>N>>M>>T;
    cin>>sx>>sy>>fx>>fy;
    for(int i=0;i<T;i++)
    {
        int x,y;
        cin>>x>>y;
        maze[x][y]=1;
    }
    dfs(sx,sy);
    cout<<sum<<endl;
    return 0;
}