首页 > 代码库 > 马拦过河卒心得体会

马拦过河卒心得体会

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

输入
一行四个数据,分别表示B点坐标和马的坐标。(保证所有的数据有解)

输出
一个数据,表示所有的路径条数。

样例输入
6 6 3 3

样例输出
6

 

分析:这种递推题想起来很简单,但很靠码代码能力,想一想很容易得出递推式map1[i][j]=map[i-1][j]+map[i][j-1](由上方和左方推得)

还有要注意越界问题,越界了的话程序会崩溃,还有就是建立一个标记图来保存马的攻击范围(8个点)。ps:马走日字

代码(有问题)

#include<bits/stdc++.h>
#define MAXN 1005
using namespace std;
int n,m,x,y; 
int map1[MAXN][MAXN];
int reg[MAXN][MAXN];//标记每一个在马的攻击范围之内的点
int atx[9]={0,1,2,2,1,-1,-2,-2,-1};
int aty[9]={0,2,1,-1,-2,-2,-1,1,2}; //马在横纵坐标所波及范围
void attack(int x,int y)
{
    for(int i=1;i<=8;i++)
    {
        if(x+atx[i]>=0&&x+atx[i]<=n&&y+aty[i]>=0&&y+aty[i]<=m)//判断是否越界,若不越界,就标记 
        reg[x+atx[i]][y+aty[i]]=-1;
    }
}//求出在攻击范围内的点(打标记) 
int main()
{
    cin>>n
    >>m;
    cin>>x
    >>y;
    attack(x,y);
    map1[0][0]=1;//将第一个 手写出来 
    for(int i=1;i<=n;i++) if(reg[i][0]==0) map1[i][0]=1;
    for(int j=1;j<=m;j++) if(reg[0][j]==0) map1[0][j]=1;//给边上赋初值 
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(reg[i][j]==0)
            {
                map1[i][j]=map1[i-1][j]+map1[i][j-1];//由左边和上面推得 
            }
        }
    }
    cout<<map1[n][m]<<endl;
    return 0;
} 

为何有错啊~

泪奔……

 

马拦过河卒心得体会