A37144. 采摘园
填空题
困难
知识点
题目描述
采摘园
题目描述：
有一个矩形的采摘园，采摘园里有N排M列果树，其中有梨树和苹果树，一天小青要去采摘园采摘果子，到了采摘园，看到提示牌写的：
1.只可以采摘苹果，梨树暂不能采摘（未成熟）；
2.采摘的起点是从采摘园中指定的某一颗苹果树；
3.从起点开始可以向上、向下、向左、向右移动（只能在采摘园中移动），且只能在苹果树下移动，不能越过梨树。
编写一个程序，计算小青从起点出发最多可到达多少棵苹果下采摘（包括起点苹果树）。
例如：矩形的采摘园种有3排4列的果树，用数字“1”表示苹果树，用数字“2”表示梨树，用数字“6”表示起点（起点也是苹果树），故从起点出发最多可到达7棵苹果下采摘（包含起点苹果树）。
如图所示：
输入描述：
第一行输入两个以一个空格隔开的正整数 N(2<N<51)，M(2<M<51)，分别表示N排M列的果树；
接下来的N行每行输入M个数字并以一个空格隔开，数字为“1”、“2”、“6”，分别表示苹果树，梨树及起点（起点也是苹果树）
输出描述：
输出一个整数，表示小青在N*M的采摘园中从起点出发最多可到达几棵苹果下采摘（包含起点苹果树）
样例输入：
3 4
2 1 2 1
1 6 1 2
1 1 1 2样例输出：
7参考答案
// 摘苹果(深搜)
#include <cstdio>
#include <iostream>
using namespace std;
int n, m, a[105][105], tj = 0;
int x1[4] = {-1, 1, 0, 0};
int y1[4] = {0, 0, -1, 1};
int dfs(int x, int y) {
for (int i = 0; i < 4; i++) {
int xx = x + x1[i];
int yy = y + y1[i];
if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && a[xx][yy] == 1) {
a[xx][yy] = 0;
tj++;
dfs(xx, yy);
}
}
}
int main() {
cin >> n >> m;
int sx, sy;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
if (a[i][j] == 6) {
a[i][j] = 0;
sx = i;
sy = j;
}
}
}
tj++;
dfs(sx, sy);
cout << tj << endl;
return 0;
}
上一题
下一题