第1个回答 2019-04-19
感觉我的程序太low了... 不知道这题到底正解是不是搜索,我感觉不是... 反正我的搜索加了一个小剪枝仍然最多在2s跑完(4,5) 这个样例. 问题是,我感觉不太会加剪枝了!... 所以(5,5)这个点一直没有跑过去. #include#include#includeusing 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;} 不过我还是把代码发上来吧,也期待别人的回答本回答被网友采纳