526互联

P1002过河卒

发布时间 2023-10-05 16:20:56作者: MLE_Automation

给出的地图从(0,0)开始，先将地图向右下方偏移，使原点变为(1,1)

cin >> n >> m >> x >> y;
m++, n++, x++, y++;//将地图向右下方偏移,让地图原点变为(0,0)

读入马的坐标后标记出所有马能走的坐标，剩下的点就是卒能走到的点

设状态dp(i,j)为从(0,0)到(i,j)的路径数量

卒可以向下或者向右走，所以到达某一点的路径数量为：到左侧点和上方点路径数量之和

可得状态转移方程

dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

完整die码：

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 25;

ll dp[N][N];
//dp[i][j]为(1,1)到当前点的路径数量

bool mp[N][N];
int dx[8] = {1, 1, -1, -1, 2, 2, -2, -2};
int dy[8] = {2, -2, 2, -2, 1, -1, 1, -1};

void solve() {
	int n, m, x, y;
	cin >> n >> m >> x >> y;
	m++, n++, x++, y++;//将地图向右下方偏移,让地图原点变为(0,0)

	dp[1][1] = 1;
	mp[x][y] = true;

	for (int i = 0; i < 8; i++){
		int xx = x + dx[i], yy = y + dy[i];
		if(xx >= 1 && xx <= n && yy >= 1 && yy <= m){
			mp[xx][yy] = true;//标记马能走到的坐标
		}
	}

	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){
			if(i == 1 && j == 1){
				continue;
			}
			dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
			if(mp[i][j]){
				dp[i][j] = 0;//无法到达，路径数量为0
			}
		}
	}

	cout << dp[n][m] << '\n';

	return;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int _ = 1;
    while(_ --) solve();

    return 0;
}