问题标题: 酷町堂：4507

Question

0

已解决

陈曦

资深天翼

#include<iostream>
using namespace std;
long long m,n,x,y,f[35][35];
bool vis[30][30];
int main(){
    cin>>n>>m>>x>>y;
    f[0][0]=1;
    for(long long i=0;i<=n;i++){
        for(long long j=0;j<=m;j++){
            if(i==x||j==y) f[i][j]=0;
            else{
                if(i-2>=0&&j-1>=0)f[i][j]+=f[i-2][j-1];
                if(i-1>=0&&j-2>=0)f[i][j]+=f[i-1][j-2];
            }
        }
    }
    cout<<f[n][m];
    return 0;
}

50分。神奇，样例没过还有50分

酷町豆刷题求解 C++ 0条评论 4 年，6 月前

Answer 1

已采纳

汪恺恒

中级启示者

注意，你这样一行一行推会少很多方案，应该一列一列推

核心

for(int j=0;j<=m;j++){
        for(int i=0;i<=n;i++){
            if(i==x||j==y) continue;  //在控制范围
            if(i==0&&j==0) f[i][j]=1;
            else{
                if(i-2>=0&&j-1>=0) f[i][j]+=f[i-2][j-1];  //四个方向
                if(i-1>=0&&j-2>=0) f[i][j]+=f[i-1][j-2];
                if(i+2>=0&&j-1>=0) f[i][j]+=f[i+2][j-1];
                if(i+1>=0&&j-2>=0) f[i][j]+=f[i+1][j-2];
            }           
        }
    }

Answer 2

周明轩

资深光能

首先，if判断的条件应该是：

if(i==0&&j==0||i==x||j==y){
                continue;
            }

其次，题目上没说不能往上走，你少判断了一个往上走的条件。

你应该同时判断{1,-2},{-1,-2},{2,-1},{-2,-1}四个方位。

望采纳，谢谢

Answer 3

汪宇航

新手启示者

???

人家说了只能往下吗

Answer 4

刘乐宸

新手天翼

1、定义dir数组
int dir[][2]={{2,1},{1,2},{-1,2},{-2,1}};

2、定义边界
f[0][0]=1;

3、进行递推
for(int j=0;j<=m;j++) {
        for(int i=0;i<=n;i++) {//fij更新其他位置 
            for(int k=0;k<4;k++) {
                int pi=i+dir[k][0],pj=j+dir[k][1];
                if(pi==x || pj==y) continue;
                if(pi>=0&&pi<=n&&pj>=0&&pj<=m)
                    f[pi][pj]+=f[i][j];
            }
        }
    }

4、输出
cout<<f[n][m];

简单明了

Answer 5

王子耀

缔造者

挺奇怪哇，样例没过50？

问题标题: 酷町堂：4507

5 个回答: