SDUT-1265 马拦过河卒

seven_ • 2023年2月21日下午10:13 • Python • 阅读 255

马拦过河卒
Time Limit: 3000 ms Memory Limit: 65536 KiB
Submit Statistic Discuss
Problem Description

棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。棋盘用坐标表示，A点（0，0）、B点（n，m）（n，m为不超过15的整数），同样马的位置坐标是需要给出的。现在要求你计算出卒从A点能够到达B点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。
Input

一行四个数据，用空格分隔，分别表示B点的坐标和马的坐标。
Output

一个数据，表示所有的路径条数。
Sample Input

6 6 3 3
Sample Output

动态规划题，稍微提了一点难度就是不可计算的点，要剔除掉，这个题目SDUT后台得到测试不是很充分。。。之前的一份代码有个很明显的错误竟然也AC了。。=_=||，不过总体来说有几个地方需要注意，例如，马在（2，2）这个位置的时候，任何输入都应该结果是0，这个可以作为测试了，还有就是不要忘记马本身的位置，以及如果马的控制点如果包括边缘上的点的时候，注意判断。

#include<stdio.h>
#include<stdlib.h>
#include<memory.h>
#include<iostream>
using namespace std;

int main(){
  int bx,by;
  int hx,hy;
  long long int map[20][20];
  cin>>bx>>by>>hx>>hy;
  memset(map,0,sizeof(map));                      //初始化整个坐标系为0
  int tempa[] = {-2,-2,-1,-1,1,1,2,2};
  int tempb[] = {-1,1,-2,2,-2,2,-1,1};      
  for(int i=0; i<8; i++)
    map[hx+tempa[i]][hy+tempb[i]] = -1;           //这是马的下一步覆盖的范围，会有八个位置
  if(hx<=bx && hy<=by)
    map[hx][hy] = -1;                             //千万不要忘记马开始的位置也要算上，因此置为-1的点共有九个（不一定全部都在bx，by范围内）
  for(int i=0; i<=bx; i++){
    for(int j=0; j<=by; j++){
        if(i==0 && j==0){                         //（0，0）位置置为1，开始依次计算
            map[i][j] = 1;
            continue;
        }
        else if(map[i][j] == -1)                  //如果该点为-1表示是控制点，就不必进行计算了
            continue;

        else{
            if((i-1)>=0 && map[i-1][j]!= -1)       //判断是否越界并且如果之前的点值不为-1时候才累加上
                map[i][j] += map[i-1][j];
            if((j-1)>=0 && map[i][j-1]!=-1)
                map[i][j] += map[i][j-1];
        }
    }
  }
  if(map[bx][by] == -1)                            //如果要求解的点已经是控制点路径数为0
    cout<<"0"<<endl;
  else
    cout<<map[bx][by]<<endl;
}