有n行m列的矩形框,填入数字123….n*m,每个数字只能能使用1次,要求左边的数字比右边的大,上边的数字比下边大,请编写程序求出有多少种填写方法。
时间: 2023-05-29 09:03:00 浏览: 165
这是一道典型的搜索问题,可以使用回溯法求解。具体思路如下:
首先定义一个二维数组board表示矩形框,将所有元素初始化为0。
从左上角开始搜索,依次枚举1~n*m这些数字,对于每个数字,先判断它是否已经在矩形框中出现过,如果出现过就跳过;否则,将它填入当前位置,并判断是否满足左边的数字比右边的大,上边的数字比下边大的要求,如果不满足就撤销填写。
当搜索到右下角时,说明找到了一种合法的填写方法,将计数器加1。
最后输出计数器即可。
代码如下:
```
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 10;
int n, m, board[MAXN][MAXN], cnt;
void dfs(int x, int y, int num) {
if (x == n && y == m) { // 搜索到右下角,找到一种合法方案
cnt++;
return;
}
if (board[x][y]) { // 当前位置已经有数字,跳过
if (y == m) dfs(x + 1, 1, num);
else dfs(x, y + 1, num);
return;
}
for (int i = num + 1; i <= n * m; i++) { // 枚举未填写的数字
bool flag = true;
for (int j = 1; j < x; j++) // 检查上面的数字
if (board[j][y] && board[j][y] < i) {
flag = false;
break;
}
for (int j = 1; j < y; j++) // 检查左边的数字
if (board[x][j] && board[x][j] < i) {
flag = false;
break;
}
if (flag) { // 如果满足要求,填入数字,继续搜索
board[x][y] = i;
if (y == m) dfs(x + 1, 1, i);
else dfs(x, y + 1, i);
board[x][y] = 0; // 撤销填写
}
}
}
int main() {
cin >> n >> m;
memset(board, 0, sizeof(board));
cnt = 0;
dfs(1, 1, 0);
cout << cnt << endl;
return 0;
}
```
需要注意的是,在dfs函数中,我们用flag变量表示当前枚举的数字是否满足左边的数字比右边的大,上边的数字比下边大的要求。如果不满足,就直接跳过,否则才填入数字并继续搜索。这个检查过程比较繁琐,需要检查上面和左边的所有数字,但是由于n和m都比较小,所以时间复杂度仍然是可以接受的。