萌新刚学OI一天,40分dfs求助
查看原帖
萌新刚学OI一天,40分dfs求助
561949
syr1125楼主2022/12/27 17:32
#include <bits/stdc++.h>
using namespace std;

int n, m, T, a[105][105], vis[105][105], dis[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}, ans = 0;
int r1, r2, c1, c2;

void dfs(int x, int y, int step)
{
	if (step > T)
	{
		return;
	}
	
	if (step == T && x == c1 && y == c2)
	{
		ans ++;
		return;
	}
	
	for (int i = 0; i < 4; i ++)
	{
		int tx = x + dis[i][0], ty = y + dis[i][1];
		if (tx <= n && tx >= 1 && ty <= m && ty >= 1 && a[tx][ty] && !vis[tx][ty])
		{
			vis[tx][ty] = 1;
			dfs(tx, ty, step + 1);
			vis[tx][ty] = 0;
		}
	}
}

int main()
{
	cin >> n >> m >> T;
	for (int i = 1; i <= n; i ++)
	{
		string x;
		cin >> x;
		for (int j = 1; j <= m; j ++)
		{
			a[i][j] = (x[j - 1] == '.') ? 1 : 0;
		}
	}
	cin >> r1 >> r2 >> c1 >> c2;
	
	vis[r1][r2] = 1;
	dfs(r1, r2, 0);
	
	cout << ans << endl;
	return 0;
}

2022/12/27 17:32
加载中...