[数据结构与算法]算法竞赛进阶指南-Gerald and Giant Chess

//用0代表白色的格子，1代表黑色的格子



int func(vector<vector<int>> mat)
{
	int m = mat.size();
	int n = mat[0].size();

	vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
	for (int i = 1; i <= m; i++)dp[i][1] = 1;
	for (int i = 1; i <= n; i++)dp[1][i] = 1;
	for (int i = 2; i <= m;i++)
	for (int j = 2; j <= n; j++)
		dp[i][j] = dp[i-1][j] + dp[i][j-1];

	vector<vector<int>> vec;
	for (int i = 0; i < m; i++){
		for (int j = 0; j < n; j++){
			if (mat[i][j] == 1)vec.push_back({ i + 1, j + 1 });
		}	
	}
	int N = vec.size();

	vector<int> dp2(N + 1, 0);

	for (int i = 1; i <= N; i++)
	{
		int xi = vec[i - 1][0];
		int yi = vec[i - 1][1];
		int sum = 0;
		for (int j = 1; j < i; j++)
		{
			int xj = vec[j - 1][0];
			int yj = vec[j - 1][1];
			if (xj <= xi && yj <= yi){
				int r = xi - xj + 1;
				int c = yi - yj + 1;
				sum += dp2[j] * dp[r][c];
			}
		}
		dp2[i]= dp[xi][yi] - sum;
	}

	int S = 0;
	for (int i = 1; i <= N; i++)
	{
		int xi = vec[i - 1][0];
		int yi = vec[i - 1][1];
		int r = m - xi + 1;
		int c = n - yi + 1;
		S += dp2[i] * dp[r][c];
	}
	return dp[m][n]-S;
}

int main() 
{
	vector<vector<int>> mat = { { 0, 0, 0 }, { 0, 1, 0 }, { 0, 0, 0 } };
	int res = func(mat);
	cout << res << endl;
	system("pause");
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖