2912: 练65.2 跳房子
内存限制：64 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
奶牛们按不太传统的方式玩起了小孩子们玩的"跳房子"游戏。奶牛们创造了一个$5×5$的、由与$x$,$y$轴平行的数字组成的直线型网格，而不是用来在里面跳的、线性排列的、带数字的方格。 然后他们熟练地在网格中的数字中跳：向前跳、向后跳、向左跳、向右跳(从不斜过来跳)，跳到网格中的另一个数字上。他们再这样跳啊跳(按相同规则)，跳到另外一个数字上(可能是已经跳过的数字)。 一共在网格内跳过五次后，他们的跳跃构建了一个六位整数(可能以$0$开头，例如$000201$)。 求出所有能被这样创造出来的不同整数的总数。
输入
第$1$到$5$行: 这样的网格，一行$5$个整数。
输出
第$1$行: 能构建的不同整数的总数。
样例输入 复制
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 2 1
1 1 1 1 1样例输出 复制
15提示
#include<bits/stdc++.h>
using namespace std;
int Map[5][5];
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
set <int> res;
void dfs(int x, int y, int step, int number) {
if (step == 5) {
res.insert(number);
return;
}
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (0 <= nx && nx < 5 && 0 <= ny && ny < 5) {
dfs(nx, ny, step + 1, 10 * number + Map[nx][ny]);
}
}
}
int main() {
for (int i = 0; i < 5; i++)
for (int j = 0; j < 5; j++)
cin >> Map[i][j];
res.clear();
for (int i = 0; i < 5; i++)
for (int j = 0; j < 5; j++)
dfs(i, j, 0, Map[i][j]);
cout << res.size() << endl;
return 0;
}