40分求助!
查看原帖
40分求助!
1028395
Oct10th楼主2023/7/10 19:03
#include <iostream>
#include <vector>

using namespace std;

struct Pos {
	int x, y;
};

Pos ma, tgt;
// count 存储可到达这一点的路径数
unsigned long count[100][100] = { 0 };
// inCtrl 标记每一点是否为控制点
bool inCtrl[100][100] = { false };

int main(void) {
	//输入
	cin >> tgt.x >> tgt.y >> ma.x >> ma.y;

	//标记控制点
	inCtrl[ma.x][ma.y] = true;
	inCtrl[ma.x + 1][ma.y + 2] = true;
	inCtrl[ma.x + 2][ma.y + 1] = true;
	if (ma.y >= 1)
		inCtrl[ma.x + 2][ma.y - 1] = true;
	if (ma.y >= 2)
		inCtrl[ma.x + 1][ma.y - 2] = true;
	if (ma.x >= 1 && ma.y >= 2)
		inCtrl[ma.x - 1][ma.y - 2] = true;
	if (ma.x >= 2 && ma.y >= 1)
		inCtrl[ma.x - 2][ma.y - 1] = true;
	if (ma.x >= 2)
		inCtrl[ma.x - 2][ma.y + 1] = true;
	if (ma.x >= 1)
		inCtrl[ma.x - 1][ma.y + 2] = true;

	for (int i = 0; i <= tgt.x; i++) {
		for (int j = 0; j <= tgt.y; j++) {
			if (i == 0) {
				if (j == 0) {
					::count[i][j] = 1; // count[0][0] = 0
				}
				else {
					::count[i][j] = ::count[i][j - 1]; // count[0][j] = count[0][j-1]
				}
				continue;
			}

			if (j == 0) {
				::count[i][j] = ::count[i - 1][j]; // count[i][0] = count[i-1][0]
				continue;
			}

			if (inCtrl[i][j]) {
				::count[i][j] = 0; //当此点为控制点时,路径数设置为 0
				continue;
			}

			::count[i][j] = ::count[i - 1][j] + ::count[i][j - 1];
		}
	}

	cout << ::count[tgt.x][tgt.y] << endl;
}
2023/7/10 19:03
加载中...