Question

c++程序设计有一个n×m的矩阵,把1，2，3…………n×m个自然数填入矩阵中，每个格子填一个数，

c++程序设计有一个n×m的矩阵,把1，2，3…………n×m个自然数填入矩阵中，每个格子填一个数，要求做到每一行右边的数比左边的数大，每一列下面的数比上面的数大，求出所有的填法，m，n小于等于5
输入n m，输出填法总数
例如：
输入：2 3
输出：5

Answer 1

感觉我的程序太low了...

不知道这题到底正解是不是搜索,我感觉不是...

反正我的搜索加了一个小剪枝仍然最多在2s跑完(4,5) 这个样例.

问题是,我感觉不太会加剪枝了!...

所以(5,5)这个点一直没有跑过去.

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int maxn=6;

int n,m,nm,Idex;
int a[maxn][maxn];
bool used[maxn*maxn];

void dfs(int x,int y){
    //如果x>n了说明整个棋盘填完了,将答案+1
    if(x>n){ Idex++;return;}
    
    //Min表示这个位置上能填的最小值,Max表示能填的最大值
    
    int Min=max(a[x-1][y],a[x][y-1])+1;
    Min=max(Min,x*y);
    //Min必须比这一列的前一个大,必须比这一行的前一个大
    //Min必须比x*y大,因为它是x*y的矩阵中最大的一个
    
    int Max=nm-(n-x+1)*(m-y+1)+1;
    //Max必须小于nm-(n-x+1)*(m-y+1)+1,因为它是右下角这个矩形里最小的一个
    
    for(int i=Min;i<=Max;i++){
        if(!used[i]){//每个数字只能填写一次
            a[x][y]=i;    //记录在数组中
            used[i]=true;  //标记数字已经被选
            if(y==m) dfs(x+1,1);//如果这一行填完了,就填下一行
            else dfs(x,y+1); //不然填这一行的下一列
            used[i]=false;    //回溯
        }
    }
}

int main(){
    
    scanf("%d%d",&n,&m);
    nm=n*m;
    dfs(1,1);
    printf("%d",Idex);
    
    return 0;
}

不过我还是把代码发上来吧,也期待别人的回答