/ Vijos / 题库 / 马拦过河卒 /

题解

294 条题解

  • 3
    @ 2017-05-08 08:57:56 
    /*
递推即可
注意两个边界处理(即0行的递推和0列的递推)
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main()
{
    int i,j,x,y,n,m,f[100][100];
    long long ans[100][100];
    scanf("%d%d%d%d",&n,&m,&x,&y);
    memset(f,1,sizeof(f));
    memset(ans,0,sizeof(ans));
    ans[0][0]=1;
    f[x][y]=0,f[x+1][y+2]=0,f[x-1][y+2]=0;
    f[x+1][y-2]=0,f[x-1][y-2]=0,f[x+2][y+1]=0;
    f[x-2][y+1]=0,f[x+2][y-1]=0,f[x-2][y-1]=0;
    for (i=1; i<=n; i++)
        if (f[i][0])
            ans[i][0]=1;
        else break;
    for (i=1; i<=m; i++)
        if (f[0][i])
            ans[0][i]=1;
        else break;
    for (i=1; i<=n; i++)
        for (j=1; j<=m; j++)
            if (f[i][j])
                ans[i][j]=ans[i-1][j]+ans[i][j-1];
    printf("%lld\n",ans[n][m]);
    return 0;
}
  • 1
    @ 2022-08-10 15:43:20 
    #include<bits/stdc++.h>
using  namespace std;
typedef long long ll;
const ll N=50005;
ll i,j,m,n,x,y,b[25][25]={0};
ll c[9]={0,-2,2,-2,2,1,-1,-1,1},d[9]={0,1,-1,-1,1,-2,2,-2,2};
bool a[25][25]={0};
int main()
{
    cin>>m>>n>>x>>y;
    m+=2;n+=2;x+=2;y+=2;
    a[x][y]=1;b[2][1]=1;
    for(i=1;i<=8;i++)a[x+c[i]][y+d[i]]=1;
    for(i=2;i<=m;i++)
    {
        for(j=2;j<=n;j++)
        {
            if(a[i][j]==1)
            {
                b[i][j]=0;
                continue;
            }
            b[i][j]=b[i-1][j]+b[i][j-1];
        }
    }
    cout<<b[m][n];
    return 0;
}
  • 1
    @ 2017-11-24 20:07:21

    //直接dfs

    #include<iostream>
    #include<cstdio>

    using namespace std;

    int a[20][20]={0};
    int m,n,s,t,x,y;

    void dfs(int aa,int bb)
    {
    if(aa==m&&bb==n){
    t++;
    return;
    }
    for(int i=0;i<=1;i++)
    for(int j=0;j<=1;j++)
    if(a[aa+i][bb+j]==0&&i+j==1&&aa+i<=m&&bb+j<=n)
    dfs(aa+i,bb+j);
    }
    int main()
    {
    cin>>m>>n>>x>>y;
    {if(x-2>=0&&y-1>=0) a[x-2][y-1] = 1;
    if(x-2>=0&&y+1>=0) a[x-2][y+1] = 1;
    if(x-1>=0&&y+2>=0) a[x-1][y+2] = 1;
    if(x-2>=0&&y+1>=0) a[x-1][y-2] = 1;
    if(x+1>=0&&y+2>=0) a[x+1][y+2] = 1;
    if(x+2>=0&&y+1>=0) a[x+2][y+1] = 1;
    if(x+2>=0&&y-1>=0) a[x+2][y-1] = 1;
    if(x+1>=0&&y-2>=0) a[x+1][y-2] = 1;
    }

    a[x][y] = 1;
    t = 0;
    dfs(0,0);
    cout<<t;
    return 0;
    }

  • 0
    @ 2023-08-13 11:36:19 
    #include<bits/stdc++.h>
using namespace std;
int n,m,a,b;
long long c[22][22];
bool ok(int x,int y){
    if((x==a)&&(y==b)){
        return 1;
    }
    if((abs(x-a)==2)&&(abs(y-b)==1)){
        return 1;
    }
    if((abs(x-a)==1)&&(abs(y-b)==2)){
        return 1;
    }
    return 0;
}
long long dfs(int x,int y){
    if((x>n)||(y>m)){
        return 0;
    }
    if((x==n)&&(y==m)){
        c[x][y]=1;
        return 1;
    }
    if(c[x][y]!=-1){
        return c[x][y];
    }
    if(ok(x,y)){
        c[x][y]=0;
        return 0;
    }
    c[x][y]=dfs(x+1,y)+dfs(x,y+1);
    return c[x][y];
}
int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    memset(c,-1,sizeof(c));
    cin>>n>>m>>a>>b;
    cout<<dfs(0,0)<<endl;
    return 0;
}
  • 0
    @ 2023-08-13 11:35:06 
    #include<bits/stdc++.h>
using namespace std;
int n,m,a,b;
long long c[22][22];
bool ok(int x,int y){
    if((x==a)&&(y==b)){
        return 1;
    }
    if((abs(x-a)==2)&&(abs(y-b)==1)){
        return 1;
    }
    if((abs(x-a)==1)&&(abs(y-b)==2)){
        return 1;
    }
    return 0;
}
long long dfs(int x,int y){
    if((x>n)||(y>m)){
        return 0;
    }
    if((x==n)&&(y==m)){
        c[x][y]=1;
        return 1;
    }
    if(c[x][y]!=-1){
        return c[x][y];
    }
    if(ok(x,y)){
        c[x][y]=0;
        return 0;
    }
    c[x][y]=dfs(x+1,y)+dfs(x,y+1);
    return c[x][y];
}
int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    memset(c,-1,sizeof(c));
    cin>>n>>m>>a>>b;
    cout<<dfs(0,0)<<endl;
    return 0;
}
  • 0
    @ 2021-07-08 15:54:50

    #include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<iomanip>
    using namespace std;
    long long a[30][30];
    int g[30][30];
    int u[8][2]={{2,1},{1,2},{2,-1},{1,-2},{-2,-1},{-1,-2},{-2,1},{-1,2}};
    int main()
    {
    memset(g,0,sizeof(g));
    int n,m,cx,cy,i,j,x,y;
    scanf("%d%d",&m,&n);
    scanf("%d%d",&x,&y);
    g[x][y]=1;
    a[x][y]=0;
    for(i=0;i<=7;i++)
    {
    cx=x+u[i][0];
    cy=y+u[i][1];
    if(cx>=0&&cx<=m&&cy>=0&&cy<=n)
    {
    g[cx][cy]=1;
    a[cx][cy]=0;
    }
    }
    a[0][0]=0;
    for(i=0;i<=m;i++)
    {
    if(g[i][0]==1)
    {
    while(i<=m)
    {
    a[i][0]=0;
    i++;
    }
    }
    else a[i][0]=1;
    }
    for(i=0;i<=n;i++)
    {
    if(g[0][i]==1)
    {
    while(i<=n)
    {
    a[0][i]=0;
    i++;
    }
    }
    else a[0][i]=1;
    }

    for(i=1;i<=m;i++)
    {
    for(j=1;j<=n;j++)
    {
    if(g[i][j]==0)
    a[i][j]=a[i-1][j]+a[i][j-1];
    }
    }
    cout<<a[m][n];
    return 0;
    }

  • 0
    @ 2021-06-28 08:02:50 
    #include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 52;
const int dx[9] = {0, -2, -1, 1, 2, 2, 1, -1, -2}, dy[9] = {0, 1, 2, 2, 1, -1, -2, -2, -1};
int n, m, l, r, p, t, k, ans, sum, tot, cnt, a[N], b[N], c[N], f[N][N], g[N][N];
inline int read()
{
    register int x = 0, f = 1;
    char ch = getchar();
    while(!isdigit(ch))
    {
        if(ch == '-') f=-1;
        ch = getchar();
    }
    while(isdigit(ch))
    {
        x=(x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
signed main()
{
    int A = read() + 1, B = read() + 1,C = read() + 1, D = read() + 1;
    f[1][1] = 1;
    g[C][D] = 1;
    for(int i = 1; i <= 8; i++)
    {
        g[C + dx[i]][D + dy[i]] = 1;
    }
    for(int i = 1; i <= A; i++)
    {
        for(int j = 1; j <= B; j++)
        {
            if(!g[i][j]) f[i][j] = max(f[i][j], f[i - 1][j] + f[i][j - 1]);
        }
    }
    cout << f[A][B];
    return 0;
}
  • 0
    @ 2020-04-08 23:56:37 
    #include <iostream>         //[2002普及组-D]过河卒
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 22;
typedef long long ll;
int n, m, X, Y;
ll dp[MAXN][MAXN];

void ini(int X, int Y)
{
    int p[8][2] = {{2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1}};
    dp[X][Y] = 0;
    int a, b;
    for (int i = 0; i < 8; i++)
    {
        a = X + p[i][0];
        b = Y + p[i][1];
        if(a >= 0 && a <= n)
            if(b >= 0 && b <= m)
                dp[a][b] = 0;
    }
}

int main()
{
    cin >> n >> m >> X >> Y;
    memset(dp, -1, sizeof(dp));
    ini(X, Y);
    for (int i = 1; i <= n; i++)
    {
        if(dp[i][0] == 0)
            break;
        dp[i][0] = 1;
    }
    for (int i = 1; i <= m; i++)
    {
        if(dp[0][i] == 0)
            break;
        dp[0][i] = 1;
    }

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if(dp[i][j])
                dp[i][j] = max((ll)0, dp[i - 1][j]) + max((ll)0,dp[i][j - 1]);

    cout << dp[n][m] << endl;

    return 0;
}
  • 0
    @ 2019-03-10 11:25:35 
    #include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f;
int d[16][16],bx,by,hx,hy;
int t[2][9] = {{0,1,1,-1,-1,2,2,-2,-2},{0,2,-2,2,-2,1,-1,1,-1}};
int main(){
    ios::sync_with_stdio(false);
    cin>>bx>>by>>hx>>hy;
    for(int i=0;i<9;i++){
        int x=hx+t[0][i],y=hy+t[1][i];
        if(x>=0&&x<=bx&&y>=0&&y<=by){
            d[x][y] = -inf;
        }
    }
    d[0][0] = 1;
    for(int i=0;i<=bx;i++){
        for(int j=0;j<=by;j++){
            if(d[i][j]==-inf) continue;
            if(i&&j) d[i][j]=d[i][j-1]+d[i-1][j];
            if(i) d[i][j]=max(d[i][j],d[i-1][j]);
            if(j) d[i][j]=max(d[i][j],d[i][j-1]);
        }
    }
    cout<<d[bx][by];
    return 0;
}
  • 0
    @ 2017-11-28 18:02:13 
    #include<stdio.h>
#include<math.h>
long long a[100][100]={{0}};
long long n,m,_n,_m;
int main() {
    scanf("%lld%lld%lld%lld",&n, &m, &_n, &_m);
    n++,m++,_n++,_m++;
    a[0][1]=1;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            if((fabs(i-_n)+fabs(j-_m)==3)&&(i!=_n)&&(j!=_m)||(i==_n&&j==_m))
                continue;
            else a[i][j]=a[i-1][j]+a[i][j-1];
    printf("%lld", a[n][m]);
    return 0;
}
  • 0
    @ 2017-11-21 20:38:25 
    #include <iostream>
#include<cstdlib>
#include<cstdio>
#include<map>
#include<vector>
#include<cstring>
#include<algorithm>
#define mod 7654321
#define FOR(i,x,y) for(i=x;i<=y;++i)
#define maxa 10000+100
using namespace std;
int n,m,p,q,ans = 0;
struct node
{
    int x,y;
};
vector<node >v;
bool check(int x,int y)
{
    int i,j;
    if(x==p&&y==q)
        return false;
    FOR(i,-1,1)
    for(j=-2;j<=2;j+=4)
    if(i!=0)
    {
        int np =p+i;
    int nq = q+j;
    if(x==np&&y==nq)
        return false;
    }
     FOR(i,-1,1)
    for(j=-2;j<=2;j+=4)
    if(i!=0)
    {
        int np =p+j;
    int nq = q+i;
    if(x==np&&y==nq)
        return false;
    }
    return true;
}
bool check1(int x,int y)
{
    int i;
    FOR(i,0,v.size()-1)
    if(x==v[i].x&&y==v[i].y)
        return false;
    return true;
}
void dfs(int x,int y)
{
   // cout<<x<<" "<<y<<endl;
    if(x>n)
        return ;
    if(y>m)
        return ;
    if(x==n&&y==m)
    {
        ans++;
        return ;
    }
    else
    {
        if(check1(x,y+1))
        dfs(x,y+1);
        if(check1(x+1,y))
        dfs(x+1,y);
    }
}
int main()
{
    cin>>n>>m>>p>>q;
    int np,nq;
    v.push_back(node{p,q});
    int i,j;
     FOR(i,-1,1)
    for(j=-2;j<=2;j+=4)
    if(i!=0)
    {
        int np =p+i;
    int nq = q+j;
    v.push_back(node{np,nq});
    np = p+j;
    nq =  q+i;
    v.push_back(node{np,nq});
    }
    /* FOR(i,0,v.size()-1)
     cout<<v[i].x<<" "<<v[i].y<<endl;*/
    dfs(0,0);
    cout<<ans<<endl;
}
  • 0
    @ 2017-10-24 23:11:01

    被H2O坑了两次

    #include<iostream>

using namespace std;

const int maxn=1010;
int dp[maxn][maxn]={0},map[maxn][maxn]={0};
int n,m,x,y;

int main()
{
    scanf("%d%d%d%d",&n,&m,&x,&y);
    x+=1;
    y+=1;
    n+=1;
    m+=1;
    map[x][y]=1;
    map[x+2][y+1]=1;
    map[x+2][y-1]=1;
    map[x+1][y+2]=1;
    map[x+1][y-2]=1;
    map[x-2][y+1]=1;
    map[x-2][y-1]=1;
    map[x-1][y+2]=1;
    map[x-1][y-2]=1;
    /*for(int i=1;i<=n;++i)
    {
        if(map[i][1]==0)dp[i][1]=1;
    }
    for(int i=1;i<=m;++i)
    {
        if(map[1][i]==0)dp[1][i]=1;
    }*/
    dp[1][1]=1;
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            if(map[i][j]!=1&&dp[i][j]==0)dp[i][j]=dp[i][j-1]+dp[i-1][j];
        }
    }
    printf("%d",dp[n][m]);
    return 0;
}
  • 0
    @ 2017-10-02 16:33:55 
    //注意边界
#include<iostream>
using namespace std;
int map[18][18],pan[18][18],z[18][18],bx[9]={0,1,1,-1,-1,2,2,-2,-2},by[9]={0,2,-2,2,-2,1,-1,1,-1};
int main()
{
    int n,m,x,y,i,k;
    cin>>n>>m>>x>>y;
    for(i=0;i<=8;i++)
    {
        int nx,ny;
        nx=x+bx[i];
        ny=y+by[i];
        if(nx>=0&&nx<=m&&ny>=0&&ny<=n)
        pan[nx][ny]=1;
    }
    z[0][0]=1;
    for(i=0;i<=n;i++)
     for(k=0;k<=m;k++)
      {
        if(i==0&&k==0)
         continue;
        if(pan[i][k])
         continue;
        if(i==0)
         {
          z[i][k]=z[i][k-1];
          continue;
         }
        if(k==0)
         {
          z[i][k]=z[i-1][k];
          continue;
         }
         z[i][k]=z[i-1][k]+z[i][k-1];
      } 
      cout<<z[n][m];
    return 0;
}
  • 0
    @ 2017-07-18 21:57:45

    #include "stdio.h"
    #include "stdlib.h"
    #include "iostream"

    using namespace std;

    int main () {
    int ma[105][105]={0},wa[105][105]={0},b1,b2,m1,m2,i,j;
    int d[2][8]={-2,-2,-1,-1,1,1,2,2,
    1,-1,2,-2,2,-2,1,-1};

    scanf("%d%d%d%d",&b1,&b2,&m1,&m2);
    for(i = 0; i <= 1; i ++)
    for(j = 0; j <= 7; j ++) {
    ma[m1+d[0][j]][m2+d[1][j]]=1;
    }
    ma[m1][m2]=1;
    wa[0][1]=1;wa[1][0]=1;

    for(i = 0; i <= b1; i ++) {
    for(j = 0; j <= b2; j ++) {
    if((ma[i][j]==0)&&(ma[i][j-1]==0)&&(j-1>=0)) {
    wa[i][j]=wa[i][j]+wa[i][j-1];
    }
    if((ma[i][j]==0)&&(ma[i-1][j]==0)&&(i-1>=0)) {
    wa[i][j]=wa[i][j]+wa[i-1][j];
    }
    /* printf("%d ",wa[i][j]); 注释语句皆为调试语句 /
    }
    /     printf("\n"); */
    }

    printf("%d",wa[b1][b2]);
    return 0;
    }
    #include "stdio.h"
    #include "stdlib.h"
    #include "iostream"

    using namespace std;

    int main () {
    int ma[105][105]={0},wa[105][105]={0},b1,b2,m1,m2,i,j;
    int d[2][8]={-2,-2,-1,-1,1,1,2,2,
    1,-1,2,-2,2,-2,1,-1};

    scanf("%d%d%d%d",&b1,&b2,&m1,&m2);
    for(i = 0; i <= 1; i ++)
    for(j = 0; j <= 7; j ++) {
    ma[m1+d[0][j]][m2+d[1][j]]=1;
    }
    ma[m1][m2]=1;
    wa[0][1]=1;wa[1][0]=1;

    for(i = 0; i <= b1; i ++) {
    for(j = 0; j <= b2; j ++) {
    if((ma[i][j]==0)&&(ma[i][j-1]==0)&&(j-1>=0)) {
    wa[i][j]=wa[i][j]+wa[i][j-1];
    }
    if((ma[i][j]==0)&&(ma[i-1][j]==0)&&(i-1>=0)) {
    wa[i][j]=wa[i][j]+wa[i-1][j];
    }
    /* printf("%d ",wa[i][j]); 注释语句皆为调试语句 /
    }
    /     printf("\n"); */
    }

    printf("%d",wa[b1][b2]);
    return 0;
    }

  • 0
    @ 2017-07-10 17:35:33

    没有判断边界居然AC了。。。

    #include<cstdio>
#include<cstring>
bool control[21][21];
int bx,by,hx,hy,f[21][21];
int main()
{
    memset(f,0,sizeof(f));
    f[0][0]=1;
    scanf("%d%d%d%d",&bx,&by,&hx,&hy);
    control[hx][hy]=1;
    control[hx-2][hy-1]=1;control[hx-2][hy+1]=1;control[hx-1][hy+2]=1;control[hx-1][hy-2]=1;
    control[hx+2][hy-1]=1;control[hx+2][hy+1]=1;control[hx+1][hy+2]=1;control[hx+1][hy-2]=1;
    for(int i=0;i<=bx;i++)
    for(int j=0;j<=by;j++)
    {
        if(i>0&&!control[i][j]) f[i][j]+=f[i-1][j];
        if(j>0&&!control[i][j]) f[i][j]+=f[i][j-1];
    }
    printf("%d\n",f[bx][by]);
    return 0;
}

    其中计算马的控制点的方法应该是这样比较恰当

    int x[8]={-2,-2,-1,-1,1,1,2,2};
int y[8]={-1,1,-2,2,-2,2,1,-1};
/*
......
*/
for(i=0;i<8;i++) {
        if((y[i]+hy)>=0&&(y[i]+hy)<=20&&(x[i]+hx)>=0&&(x[i]+hx)<=20) {
            control[y[i]+hy][x[i]+hx]=1;
        }
    }
  • 0
    @ 2017-01-22 15:43:38

    #include<iostream>
    #include<cstdio>
    using namespace std;
    int a[20][20];
    bool b[20][20];
    void f(int x,int c)
    {
    for(int i=1;i<16;i++)
    {
    for(int j=1;j<16;j++)
    {
    if(b[i][j]==1) a[i][j]=a[i-1][j]+a[i][j-1];
    }
    }
    }
    int main()
    {
    int n,m,x,y;
    for(int i=0;i<16;i++)
    for(int j=0;j<16;j++)
    {
    a[i][j]=0;b[i][j]=1;
    }
    scanf("%d%d%d%d",&n,&m,&x,&y);
    if(x>=0&&y>=0)b[x][y]=0;
    if(x+2<=15&&y+1<=15)b[x+2][y+1]=0;
    if(x+2<=15&&y-1>=0)b[x+2][y-1]=0;
    if(x+1<=15&&y+2<=15)b[x+1][y+2]=0;
    if(x+1<=15&&y-2>=0)b[x+1][y-2]=0;
    if(x-1>=0&&y+2<=15)b[x-1][y+2]=0;
    if(x-1>=0&&y-2>=0)b[x-1][y-2]=0;
    if(x-2>=0&&y+1<=15)b[x-2][y+1]=0;
    if(x-2>=0&&y-1>=0)b[x-2][y-1]=0;
    for(int i=1;i<=n;i++)
    {
    if(i==1){if(b[i][0]!=0)a[i][0]=1;}else a[i][0]=a[i-1][0];
    }
    for(int i=1;i<=m;i++)
    {
    if(i==1){if(b[0][i]!=0)a[0][i]=1;}else a[0][i]=a[0][i-1];
    }
    f(n,m);
    printf("%d",a[n][m]);
    }

  • 0
    @ 2016-08-26 16:57:25

    #include<iostream>
    using namespace std;
    int a[20][20];
    int m,n;
    int ass=0;
    void find(int x,int y)
    {
    if((x<0)||(y<0)||(a[x][y]==-1))
    {
    return;
    }
    else if(x==0&&y==0)
    {
    ass++;
    return;
    }
    else
    {
    find(x-1,y);
    find(x,y-1);
    }
    }
    int main()
    {
    int x,y;
    cin>>m>>n>>x>>y;
    a[x][y]=-1;
    a[x-1][y-2]=-1;
    a[x-2][y-1]=-1;
    a[x+1][y+2]=-1;
    a[x+2][y+1]=-1;
    a[x-1][y+2]=-1;
    a[x-2][y+1]=-1;
    a[x+1][y-2]=-1;
    a[x+2][y-1]=-1;
    find(m,n);
    cout<<ass;
    return 0;
    }

  • 0
    @ 2016-08-16 19:42:52

    题解+代码

  • 0
    @ 2016-08-15 14:54:48

    const

    dx:array[1..8] of integer=(2,1,-1,-2,-2,-1,1,2);

    dy:array[1..8] of integer=(1,2,2,1,-1,-2,-2,-1);

    var

    f:array[0..20,0..20] of longint;

    g:array[-2..22,-2..22] of boolean;

    i,j,n,m,x,y:integer;

    begin

    readln(n,m,x,y);

    fillchar(g,sizeof(g),true);

    g[x,y]:=false;

    for i:=1 to 8 do g[x+dx[i],y+dy[i]]:=false;

    if g[0,0] then f[0,0]:=1;

    for j:=1 to m do

    if g[0,j] then f[0,j]:=f[0,j-1];

    for i:=1 to n do

    if g[i,0] then f[i,0]:=f[i-1,0];

    for i:=1 to n do

    for j:=1 to m do

    if g[i,j] then f[i,j]:=f[i-1,j]+f[i,j-1];

    writeln(f[n,m]);

    end.

  • 0
    @ 2016-08-01 11:16:54

    #include<bits/stdc++.h>
    using namespace std;
    int opt[17][17]={0};
    bool _map[17][17];
    int dx[8]={1,1,-1,-1,2,2,-2,-2};
    int dy[8]={2,-2,2,-2,1,-1,1,-1};
    int main()
    {
    int ex,ey,mx,my,nx,ny,i,j;
    memset(_map,false,sizeof(_map));
    cin>>ex>>ey>>mx>>my;
    ex++;
    ey++;
    mx++;
    my++;
    for(i=1;i<=ex;i++)
    for(j=1;j<=ey;j++)
    _map[i][j]=true;
    _map[mx][my]=false;
    for(i=1;i<=ex;i++)
    opt[i][1]=1;
    for(i=1;i<=ey;i++)
    opt[1][i]=1;
    for(i=0;i<8;i++)
    {
    nx=mx+dx[i];
    ny=my+dy[i];
    if(nx>=1&&nx<=ex&&ny>=1&&ny<=ey)
    {
    _map[nx][ny]=false;
    opt[nx][ny]=0;
    }
    }
    if(mx==1)
    {
    for(i=my;i<=ey;i++)
    opt[1][i]=0;
    }
    if(my==1)
    {
    for(i=mx;i<=ex;i++)
    opt[i][1]=0;
    }
    for(i=1;i<=ex;i++)
    for(j=1;j<=ey;j++)
    if(i==1&&j==1) continue;
    else if(_map[i][j]) opt[i][j]=opt[i-1][j]+opt[i][j-1];
    // for(i=1;i<=ex;i++)
    // {
    // for(j=1;j<=ey;j++)
    // if(i==mx&&j==my) cout<<"@"<<" ";
    // else cout<<opt[i][j]<<" ";
    // cout<<endl;
    // }
    cout<<opt[ex][ey]<<endl;
    return 0;
    }

马拦过河卒

信息

ID
1121
难度
4
分类
动态规划 点击显示
标签
递交数
9582
已通过
3785
通过率
40%
被复制
23
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1