A34374. 路线
题目描述
路线
题目描述
小蓝将多盆鲜花摆成一个M*N的矩阵，小蓝每天都会从左上角位置的花盆出发，给每一个花盆中的鲜花浇水。
已知：
1)每两个相邻的花盆之间的距离都相等；
2)每次小蓝浇水的路线都是走直线，不能走斜线；
3)除左上角花盆以外，其他花盆只能经过一次；
4)每盆花都浇过之后返回左上角位置。
当给出M和N的值，请你帮助小蓝找出一共有多少条路线可以满足以上条件，如果没有满足条件的路线输出0。
例如：M=3，N=4，一共有4条路线满足以上条件。
输入描述
输入两个正整数M，N（2≤M≤10，2≤N≤10），M表示矩阵的行数，N表示矩阵的列数，两个正整数之间以一个空格隔开
输出描述
输出一个整数，表示一共有多少条路线可以满足以上条件，如果没有满足条件的路线输出0
样例输入
3 4
样例输出
4
参考答案
// 参考代码1
#include <bits/stdc++.h>
#define N 11
using namespace std;
int a[N][N];
int n, m, ans;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
bool st[N][N];
void dfs(int x, int y, int step) {
// cout << x << ' ' << y << ' ' << step << endl;
for (int i = 0; i < 4; i++) {
int xx = x + dx[i];
int yy = y + dy[i];
if (!st[xx][yy] && 1 <= xx && xx <= n && 1 <= yy && yy <= m) {
st[xx][yy] = 1;
if (step + 1 == n * m) {
if (xx == 1 && yy == 1)
ans++;
st[xx][yy] = 0;
return;
}
dfs(xx, yy, step + 1);
st[xx][yy] = 0;
}
}
}
int main() {
scanf("%d%d", &n, &m);
if (n % 2 == 1 && m % 2 == 1) {
cout << "0" << endl;
return 0;
}
dfs(1, 1, 0);
cout << ans << endl;
return 0;
}答案解析
// 参考代码2
#include <bits/stdc++.h>
using namespace std;
int n, m, ans;
int v[15][15];
int d[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};
void dfs(int x, int y, int step) {
// cout << x << " " << y << "\n";
if (x == 1 && y == 1 && step == n * m) {
ans++;
return;
}
if (v[x][y])
return;
v[x][y] = 1;
for (int i = 0; i < 4; i++) {
int xx = d[i][0] + x;
int yy = d[i][1] + y;
if (xx > 0 && xx <= n && yy > 0 && yy <= m) {
dfs(xx, yy, step + 1);
}
}
v[x][y] = 0;
}
int main() {
cin >> n >> m;
if (n % 2 == 1 && m % 2 == 1) {
cout << 0;
return 0;
}
dfs(1, 1, 0);
cout << ans;
return 0;
}