帮我写一个C++代码:棋盘上A点有一个过河卒,需要走到目标B点。卒行走的规则:可以向下、或者向右,不能走到对方的控制点上。同时在棋盘上有K个点有对方的一个马, 马所在的点称为对方马的控制点。因此称之为 “马拦过河卒”.棋盘用坐标表示,A点(0,0),B点(n,m)。输入格式:第一行n,m,k,接下来k行每行两个数x(i),y(i)表示第i个马在(x(i),y(i))的位置。 注意不保证控制点不重合。输出一行一个数,为过河卒从A走到B的总路线个数对1000000007取模的值。 样例输入:2 3 2 1 1 1 2输出:2
时间: 2024-03-25 10:40:25 浏览: 134
一个C++程序
好的,根据您的要求,我已经为您编写了一个 C++ 程序,可以解决您提出的问题。下面是程序的代码:
```c++
#include <iostream>
#include <cstring>
using namespace std;
const int MOD = 1e9 + 7;
const int N = 1e3 + 10;
int n, m, k;
int h[N][N]; // 马的控制点
int f[N][N];
int main() {
cin >> n >> m >> k;
memset(h, 0, sizeof h);
for (int i = 0; i < k; i++) {
int x, y;
cin >> x >> y;
h[x][y] = 1;
}
f[0][0] = 1;
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
if (i == 0 && j == 0) continue;
if (i == 0) {
if (!h[i][j - 1]) f[i][j] = f[i][j - 1];
} else if (j == 0) {
if (!h[i - 1][j]) f[i][j] = f[i - 1][j];
} else {
if (!h[i][j - 1]) f[i][j] = f[i][j - 1];
if (!h[i - 1][j]) f[i][j] = (f[i][j] + f[i - 1][j]) % MOD;
}
}
}
cout << f[n][m] << endl;
return 0;
}
```
该程序的思路是使用动态规划,设 $f(i,j)$ 表示过河卒从 $(0,0)$ 走到 $(i,j)$ 的总路线数。因为过河卒只能向下或者向右走,所以 $f(i,j)$ 只能从 $f(i,j-1)$ 或者 $f(i-1,j)$ 转移而来,即:
$$
f(i,j) = \begin{cases}
f(i,j-1), & \text{if } h(i,j-1)=0 \\
f(i-1,j), & \text{if } h(i-1,j)=0 \\
f(i,j-1)+f(i-1,j), & \text{if } h(i,j-1)=h(i-1,j)=0
\end{cases}
$$
其中 $h(i,j)$ 表示点 $(i,j)$ 是否是对方的马的控制点。如果是,则不能通过该点。初始化 $f(0,0) = 1$,最终答案为 $f(n,m)$。
需要注意的是,题目要求对答案取模,因此在计算过程中需要加上取模运算。
阅读全文