自动搬运

查看原文

来自洛谷，原作者为

	zmza 少说话，祸从口出。多思考，多做事|想成功先发疯、不顾一切向钱冲。 拼一次富三代、拼命才能不失败。

搬运于2025-08-24 22:04:20，当前版本为作者最后更新于2021-07-06 10:07:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

upd on 2024.8.23：第 $28$ 行修改为 for (int j = 2; j <= c; j++)。感谢@Hollow_Knight 的指出

本题暴力的思路是：枚举每一个点，看看有哪些点可以到达这个点，这个点的方案数就是所有能到达它的点的方案数之和。

现在关键是要求有哪些点可以到达一个点了。在这个点的左上方的点都可以到达这一个点。因为题目说的是 至少。

至于第一个条件，在循环里特判一下就可以了。

这道题的加强版是一道蓝题，要用线段树，数据范围是 $r,c \leq 750$ ， 过不了。但是这道题的范围是 $r,n \leq100$ ，所以我们就直接暴力就行了。

代码：

#include<bits/stdc++.h>
#define int long long
const int mod = 1e9 + 7;
using namespace std;
int a[105][105], dp[105][105];
int read()
{
	int i = 0, f = 1;
	char ch;
	for (ch = getchar(); (ch < '0' || ch > '9') && ch != '-'; ch = getchar());
	if (ch == '-')
	{
		f = -1;
		ch = getchar();
	}
	for (; ch >= '0' && ch <= '9'; ch = getchar())
		i = (i << 3) + (i << 1) + (ch ^ 48);
	return i * f;
}
signed main()
{
	int r = read(), c = read(), k = read();
	for (int i = 1; i <= r; i++)
		for (int j = 1; j <= c; j++)
			a[i][j] = read();
	dp[1][1] = 1;
	for (int i = 2; i <= r; i++)
		for (int j = 2; j <= c; j++)
			for (int t1 = 1; t1 < i; t1++)
				for (int t2 = 1; t2 < j; t2++)
					if (a[t1][t2] != a[i][j]) dp[i][j] = (dp[i][j] + dp[t1][t2]) % mod;
	printf("%lld", dp[r][c]);
	return 0;
}