Luogu p3654 fisrt step

Topic link ：First Step

Knowledge point ： A straight line dfs
A straight line dfs It means to follow a path to the end , Can't turn .

In this problem, you can go straight to the right or down dfs.

Down dfs

void down(int x, int y)
{
	if( Meet the end condition )
	{
		 Do what you have to do ;
		return;
	}
	int newx = x + dir[0][0], newy = y + dir[0][1];// Down 
	if (newx >= 0 && newx < n && newy >= 0 && newy < m && g[newx][newy] == '.')
	{
		 Do what you have to do ;
		down(newx, newy);
	}
}

towards the right dfs It's the same way .

In this category , For each point dfs.（ It's kind of like the island issue . But the island problem is general dfs You can turn .） So we have to go through the two-dimensional matrix .

AC Code ：

#include <iostream>

using namespace std;
const int N = 110;
char g[N][N];
int dir[2][2] = {
     {
    1,0},{
    0,1}};
int n, m, k;
int ans;
int cnt;

void down(int x, int y)
{
    
	if (cnt == k - 1)
	{
    
		ans++;
		return;
	}
	int newx = x + dir[0][0], newy = y + dir[0][1];// Down 
	if (newx >= 0 && newx < n && newy >= 0 && newy < m && g[newx][newy] == '.')
	{
    
		cnt++;
		down(newx, newy);
	}
}

void right(int x, int y)
{
    
	if (cnt == k - 1)
	{
    
		ans++;
		return;
	}
	int newx = x + dir[1][0], newy = y + dir[1][1];// towards the right 
	if (newx >= 0 && newx < n && newy >= 0 && newy < m && g[newx][newy] == '.')
	{
    
		cnt++;
		right(newx, newy);
	}
}


int main()
{
    
	cin >> n >> m >> k;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> g[i][j];
	
	// Traverse every point 
	for (int i = 0; i < n; i++)
	{
    
		for (int j = 0; j < m; j++)
		{
    
			if (g[i][j] == '.')
			{
    
				down(i, j);
				cnt = 0;
				right(i, j);
				cnt = 0;
			}
		}
	}
	if (k == 1) ans /= 2;
	cout << ans;
}

notes ： In this problem , If k be equal to 1, Then the count is repeated to the right and down , Divide by 2.