[summer daily question] Luogu p1605 maze

Topic link ：P1605 maze - Luogu | New ecology of computer science education (luogu.com.cn)

Title Description

Given a N×M  The maze of squares , There is... In the maze T  Obstacles , A barrier is not accessible .

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 .

Given the coordinates of the starting point and the ending point , Each square can pass at most once , How many schemes are there from the starting point coordinate to the end point coordinate .

Input format

The first line is three positive integers N,M,T, Respectively represent the length and width of the maze and the total number of obstacles .

The second line is four positive integers SX,SY,FX,FY, among ,SX,SY  Represents the starting point coordinates ,FX,FY  Represents the coordinates of the end point .

Next T  That's ok , Two positive integers per line , Represents the coordinates of the obstacle point .

Output format

Output the total number of schemes from the start coordinate to the end coordinate .

Examples #1

The sample input #1

2 2 1
1 1 2 2
1 2

Sample output #1

1

Tips

about 100%  The data of ,1 <= N,M <= 5,1 <= T <= 10,1 <= SX,FX <= n,1 <= SY,FY <= m.

AC code:（DFS）

#include<iostream>
#include<algorithm>

using namespace std;

/*
0 0 0 0 0 0
0 1 1 1 1 0
0 1 2 2 1 0
0 1 2 * 1 0
0 1 1 1 1 0
0 0 0 0 0 0
*/
int dir[4][2]={
   {0,1}, //  Right  
		{1,0}, //  Next 
		{0,-1},//  Left 
		{-1,0}};//  On  
int a[10][10],book[10][10];
int startx,starty,endx,endy;
int cnt;
void dfs(int x,int y,int step)
{
	if(x==endx && y==endy)
	{
		cnt++;
		return ;
	}
	for(int i=0;i<4;i++)
	{
		int tx=x+dir[i][0];
		int ty=y+dir[i][1];
		if(a[tx][ty]==1 && book[tx][ty]==0)
		{
			book[tx][ty]=1;
			dfs(tx,ty,step+1);
			book[tx][ty]=0;
		}
	}
	return ;
}

int main()
{
	int n,m,t;
	cin>>n>>m>>t;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			a[i][j]=1;
	cin>>startx>>starty>>endx>>endy;
	while(t--)
	{
		int i,j;
		cin>>i>>j;
		a[i][j]=2;
	}
	book[startx][starty]=1;
	dfs(startx,starty,0);
	cout<<cnt<<endl;
	
	return 0;
}