NC369. [NOIP2002 普及组] 过河卒
描述
棋盘上 A点有一个过河卒，需要走到目标 B 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 C 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
示例1
输入:
6,6,3,3
输出:
6
示例2
输入:
5,4,2,3
输出:
3
示例3
输入:
2,5,3,5
输出:
1
C++ 解法, 执行用时: 3ms, 内存消耗: 392KB, 提交时间: 2022-05-22
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int整型 棋盘行数
* @param m int整型 棋盘列数
* @param x int整型 马的横坐标
* @param y int整型 马的纵坐标
* @return int整型
*/
/*void CrossRiverCore(int n, int m, int x, int y, int inx, int iny,int& ret) {
if (inx > n || iny > m) return;
if (inx == x && iny == y || inx == x + 2 && iny == y + 1 || inx == x + 2 && iny == y - 1 ||
inx == x - 2 && iny == y - 1 || inx == x - 2 && iny == y + 1) return;
if (inx == x - 1 && iny == y - 2 || inx == x - 1 && iny == y + 2 ||
inx == x + 1 && iny == y + 2 || inx == x + 1 && iny == y - 2)
return;
if (inx == n && iny == m) ret++;
CrossRiverCore(n, m, x, y, inx + 1, iny, ret);
CrossRiverCore(n, m, x, y, inx, iny + 1, ret);
}
int crossRiver(int n, int m, int x, int y) {
// write code here
int ret = 0;
CrossRiverCore(n, m, x, y, 0, 0, ret);
return ret;
}*/
int crossRiver(int n, int m, int x, int y) {
// write code here
int** res = new int* [2];
for (int i = 0; i < 2; i++) res[i] = new int[m + 1];
/*int res[7][7] = { 0 };*/
int oldVal = 0, newVal = 1;
for (int i = 0; i <= n; i++) {
oldVal = newVal;
newVal = 1 - oldVal;
for (int j = 0; j <= m; j++) {
bool state1 = 0;
if (i == x && j == y || i == x + 2 && j == y + 1 || i == x + 2 && j == y - 1 ||
i == x - 2 && j == y - 1 || i == x - 2 && j == y + 1 ||
i == x - 1 && j == y - 2 || i == x - 1 && j == y + 2 ||
i == x + 1 && j == y + 2 || i == x + 1 && j == y - 2)
state1 = true;
if (i == 0 || j == 0) {
if (i == 0 && j > 0) {
if (state1 == true || res[newVal][j - 1] == 0) res[newVal][j] = 0;
else res[newVal][j] = 1;
}
if (j == 0 && i > 0) {
if (state1 == true || res[oldVal][j] == 0) res[newVal][j] = 0;
else res[newVal][j] = 1;
}
if(i==0&&j==0) res[newVal][j]=1;
continue;
}
res[newVal][j] = res[oldVal][j] + res[newVal][j - 1];
if (state1 == true) res[newVal][j] = 0;
}
}
int ret = res[newVal][m];
for (int i = 0; i < 2; i++) delete[] res[i];
delete[] res;
return ret;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 408KB, 提交时间: 2022-06-19
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int整型 棋盘行数
* @param m int整型 棋盘列数
* @param x int整型 马的横坐标
* @param y int整型 马的纵坐标
* @return int整型
*/
int crossRiver(int n, int m, int x, int y) {
// write code here
//
// vector<pair<int, int>> visit;
// recursion(visit, n, m, x, y, 0, 0);
vector<vector<int>>dp(n + 1, vector<int>(m + 1, 0));
dp[0][0] = 1;
for(int i = 0; i <= n; i ++){
for(int j = 0; j <= m; j ++){
if( (abs(i - x) + abs (j - y)) == 3 && i != x && j != y){
dp[i][j] = 0;
}else if(i == x && j == y){
dp[i][j] = 0;
}else if(i > 0 && j == 0 ){
dp[i][j] = dp[i - 1][j];
}else if( j > 0 && i == 0){
dp[i][j] = dp[i][j - 1];
}else if (i > 0 && j > 0){
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
return dp[n][m];
}
// void recursion(vector<pair<int, int>> visit, int n, int m, int x, int y, int i, int j){
// if(i > n || j > m || ((abs(i - x) + abs (j - y)) == 3 && i != x && j != y)){
// visit.pop_back();
// return;
// }
// // visit[i][j] = 1;
// visit.push_back({i, j});
// // visit.insert({i, j});
// if( i == n && j == m) {
// // res ++;
// path.insert(visit);
// }
// recursion(visit, n, m, x, y, i + 1, j);
// recursion(visit, n, m, x, y, i, j + 1);
// }
};
C++ 解法, 执行用时: 3ms, 内存消耗: 444KB, 提交时间: 2022-08-02
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int整型 棋盘行数
* @param m int整型 棋盘列数
* @param x int整型 马的横坐标
* @param y int整型 马的纵坐标
* @return int整型
*/
int _x=0;
int _y=0;
int _n=0;
int _m=0;
vector<vector<int>>dp;
int crossRiver(int n, int m, int x, int y) {
// write code here
_n=n;
_m=m;
_x=x;
_y=y;
dp.resize(n+1,vector<int>(m+1,-1));
return process(0,0);
}
int process(int row,int col)
{
if(row>_n||col>_m)
{
return 0;
}
if(check(row,col))
{
return 0;
}
if(row==_n&&col==_m)
{
dp[row][col]=1;
return 1;
}
if(dp[row][col]!=-1)
{
return dp[row][col];
}
int ans=0;
ans+=process(row+1,col);
ans+=process(row,col+1);
dp[row][col]=ans;
return ans;
}
bool check(int row,int col)
{
if(abs(_x-row)+abs(_y-col)==3&&_x!=row&&_y!=col)
{
return true;
}
else if(row==_x&&col==_y)
{
return true;
}
else
{
return false;
}
}
};
C++ 解法, 执行用时: 4ms, 内存消耗: 404KB, 提交时间: 2022-08-02
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int整型 棋盘行数
* @param m int整型 棋盘列数
* @param x int整型 马的横坐标
* @param y int整型 马的纵坐标
* @return int整型
*/
vector<vector<int>>dp;
int crossRiver(int n, int m, int x, int y) {
// write code here
dp.resize(n + 1, vector<int>(m + 1,0));
return process(n, m, x, y, 0, 0);
}
int process(int n, int m, int x, int y, int row, int col) {
if (row > n || col > m) {
return 0;
}
if (Check(row, col, x, y)) {
return 0;
}
if (row == n && col == m) {
// dp[row][col]=1;
return 1;
}
//注意不能填-1因为有些点再马点中
if(dp[row][col]!=0){
cout<<row<<":"<<col<<endl;
return dp[row][col];
}
int p1 = process(n, m, x, y, row + 1, col);
int p2 = process(n, m, x, y, row, col + 1);
int ans = p1 + p2;
dp[row][col] = ans;
return ans;
}
bool Check(int i, int j, int x, int y) {
//检查是否是马点
return (abs(x - i) + abs(y - j) == 3 && i != x && j != y) || (i == x && y == j);
}
};
C++ 解法, 执行用时: 4ms, 内存消耗: 424KB, 提交时间: 2022-08-06
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int整型 棋盘行数
* @param m int整型 棋盘列数
* @param x int整型 马的横坐标
* @param y int整型 马的纵坐标
* @return int整型
*/
int crossRiver(int n, int m, int x, int y) {
// write code here
vector<vector<int>> dp(n+1,vector<int>(m+1,0));
dp[0][0]=1;
for(int i=0;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
if((abs(i-x)+abs(j-y))==3&&i!=x&&j!=y)
dp[i][j]=0;
else if(i==x&&j==y)
dp[i][j]=0;
else if(i>0&&j==0)
{
dp[i][j]=dp[i-1][j];
}else if(j>0&&i==0)
dp[i][j]=dp[i][j-1];
else if(i>0&&j>0)
{
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
}
return dp[n][m];
}
};