# Path Statistics (classical dfs to dp problem)

In the past two days, I found a very interesting topic, not that it is very difficult, but that this topic is indeed a classic dfs problem, which can be encountered by basic beginners. However, if this is only the case, this topic is not of great value to say, but it is very special that this topic is a classic dfs to dp problem, which I think is worth learning;

This question requires us to go from one point to another. Of course, the special judgment should be given priority. Secondly, let's think about the dfs method. We find that the dfs method is very simple. We only need to type the table and then traverse;

It should be noted here that the figure shows you from bottom left to top right, but when we actually correspond to the array, it is from top left to bottom right, and the path can only be down and right.

Then you can easily write dfs:

```#include<algorithm>
#include<cstring>
#include<iostream>

using namespace std;
int dx[]={0,1},dy[]={1,0};//Note that it can only be down or right
int arr[35][35];//chart
bool st[35][35];//Used to judge whether the current point can go
int x,y,ans=0;

void dfs(int a,int b)
{
if(a==x&&b==y)
ans++;//Arrive at the destination and count once

for(int i=0;i<2;i++)
{
int xx=a+dx[i],yy=b+dy[i];
if(st[xx][yy]==false&&xx<=x&&yy<=y)
{
//			cout<<xx<<' '<<yy<<endl;
dfs(xx,yy);
}

}
}

int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
ans=0;
int x1,y1,x2,y2;
cin>>x>>y>>x1>>y1>>x2>>y2;
if(x1==0&&y1==0||x2==0&&y2==0)
{
cout<<"0"<<endl;
continue;
}
st[x1][y1]=true;
st[x2][y2]=true;//You can't go here
dfs(0,0);
cout<<ans<<endl;
st[x1][y1]=false;
st[x2][y2]=false;//Eliminate marking
}

}```

At this time, we handed it in and found that it must not pass! The complexity of dfs is very high. Unfortunately, this problem doesn't even allow you to cheat points (silently condemning the teacher for one second). Then let's consider other methods. At this time, we find that for each point, his last step can only come from two places;

Speaking of this, if you don't think it's a dp, I can only say: young man (little sister), lack of strength, we have to strengthen exercise.

So we did Yan's dp analysis

Then we have the state transition equation, just mark the points that can't go and the special judgment boundary

code:

```#include<algorithm>
#include<cstring>
#include<iostream>

using namespace std;

long long int arr[35][35];//Note that the answer may explode
bool st[35][35];
int x,y;

int main()
{
memset(st,false,sizeof(st));
int n;
cin>>n;
for(int k=0;k<n;k++)
{
int x1,y1,x2,y2;
cin>>x>>y>>x1>>y1>>x2>>y2;
if(x1==0&&y1==0||x2==0&&y2==0||x1==x&&y1==y||x2==x&&y2==y)//Special judge on the road construction at home and school
{
cout<<"0"<<endl;
continue;
}

for(int i=0;i<=x;i++)
for(int j=0;j<=y;j++)
arr[i][j]=0;//Clear the last answer every time you enter

st[x1][y1]=true,st[x2][y2]=true;

for(int i=0;i<=x;i++)
{
for(int j=0;j<=y;j++)
{
if(st[i][j]!=true)
{
if(i==0&&j==0)
arr[i][j]=1;
else if(i==0)
arr[i][j]=arr[i][j-1];
else if(j==0)
arr[i][j]=arr[i-1][j];
else
arr[i][j]=arr[i-1][j]+arr[i][j-1];
//Special judgment in all cases
}
}
}

//		for(int i=0;i<=x;i++)
//		{
//			for(int j=0;j<=y;j++)
//			cout<<arr[i][j]<<' ';
//			cout<<endl;
//		}
st[x1][y1]=false,st[x2][y2]=false;
cout<<arr[x][y]<<endl;// Just output the answer directly
}

}```

At this point, the end of the flower;

Posted by kylebragger on Sat, 16 Apr 2022 12:30:19 +0300