题解

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%
被复制
25
上传者