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;

Question link: PTA | program design experiment auxiliary teaching platform

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;

Tags: C C++ Algorithm Dynamic Programming

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