BJFU小赛1334仓鼠球解题报告

描述

一日，仓鼠君在一个由10×10的格子构成的竞技场里滚球，每一块格子高度不同；
仓鼠君有特别的滚球技巧，可以每次精准地向前后左右四个方向中的一个滚动一格；
仓鼠君只能从高的格子向相邻的相同高度或更低的格子滚动；
如果两个格子高度差超过100（不含100），那么仓鼠君不能向这个格子移动，否则会摔碎自己的球；
仓鼠君不会抛弃他的球。

现在，给你每个格子的高度，问仓鼠君能够到达的所有格子的数目（包括开始时的格子）（在任何一个路线中经过的格子都算在结果中）。

输入

输入第一行是一个整数T(1<=T<=20)，代表测试数据的数量；
然后第一行是两个整数x和y，代表仓鼠君开始时的坐标(0<=x,y<=9)；
然后是一个10×10的矩阵，表示每个格子的高度(0<=h<=200)。

输出

对于每组数据在一行内输出一个整数，表示仓鼠君能够到达的所有格子数目（包括开始时的格子）（在任何一个路线中经过的格子都算在结果中）。

样例输入

1
0 0
200 199 198 197 196 195 194 193 192 191
199 198 197 196 195 194 193 192 191 190
198 197 196 195 194 193 192 191 190 189
197 196 195 194 193 192 191 190 189 188
196 195 194 193 192 191 190 189 188 187
195 194 193 192 191 190 189 188 187 186
194 193 192 191 190 189 188 187 186 185
193 192 191 190 189 188 187 186 185 184
192 191 190 189 188 187 186 185 184 183
191 190 189 188 187 186 185 184 183 182

样例输出

100

提示

仓鼠君能够在不同路线中走到所有的格子，故结果为100。

分析：

可以用递归模拟仓鼠君的路线，每走一步都有相同的选择，走过的位置就不再重复。

代码：

#include<stdio.h>
#include<string.h>
#define N 10
int a[N][N];
int vis[N][N];
int func(int x, int y, int f) {
int sum = 0;
if (x >= 10 || x < 0 || y >= 10 || y < 0 || vis[x][y])
return sum;
if (!f) {
//star position
sum++;
vis[x][y] = 1;
} else if (f == 1) {
if (a[x - 1][y] >= a[x][y]) {
if (a[x - 1][y] - a[x][y] <= 100) {
vis[x][y] = 1;
sum++;
} else
return 0;
} else
return 0;
} else if (f == 2) {
if (a[x + 1][y] >= a[x][y]) {
if (a[x + 1][y] - a[x][y] <= 100) {
vis[x][y] = 1;
sum++;
} else
return 0;
} else
return 0;
} else if (f == 3) {
if (a[x][y - 1] >= a[x][y]) {
if (a[x][y - 1] - a[x][y] <= 100) {
vis[x][y] = 1;
sum++;
} else
return 0;
} else
return 0;
} else if (f == 4) {
if (a[x][y + 1] >= a[x][y]) {
if (a[x][y + 1] - a[x][y] <= 100) {
vis[x][y] = 1;
sum++;
} else
return 0;
} else
return 0;
}
sum += func(x + 1, y, 1); //right
f=1
sum += func(x - 1, y, 2); //left
f=2
sum += func(x, y + 1, 3); //up
f=3
sum += func(x, y - 1, 4); //down
f=4
return sum;
}
int main() {
int t, x, y;
//
freopen("Data.txt", "r", stdin);
//
freopen("Out.txt", "w", stdout);
scanf("%d", &t);
while (t--) {
scanf("%d%d", &x, &y);
memset(vis, 0, sizeof(vis));
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
scanf("%d", &a[i][j]);
}
}
printf("%dn", func(x, y, 0));
}
return 0;
}