计算机能力挑战赛—程序设计 智能除草 题目解析

文章目录

  • 前言
  • 一、题目
  • 二、解题
    • 1.思路
    • 2.代码
  • 总结

前言

计算机能力挑战赛程序设计中的一道题目，上手做了一下午，有了一些思考和体会，网上关于此题的讲解较少，故想将自己的思路发在网上供大家参考，代码如果存在一些问题，欢迎大家在评论区指出，一起讨论，共同进步！

一、智能除草题目

农业植保无人机作为最新的设备，可以加注除草剂进行除草。每次工作可以喷洒边长为K的正方形区域。现有一块边长为N的正方形农田，将其分成N*N个方格单元，已知每个单元里的杂草数量。求该植保无人机一次工作最多可以除草的数量。

输入说明：
第一行是2个正整数，分别为N和K（1≤K≤N≤1000）。
之后N行N列正整数，表示每个单元中的杂草数量（不超过50）。
输出说明：
该植保无人机一次工作最多可以除草的数量。

输入样例：
5 2
2 2 1 1 1
1 2 1 5 6
6 1 1 4 5
2 6 1 1 1
1 1 1 1 1
输出样例：
20

按照最后一次提交的代码为评分标准。

二、解题

1.思路

本题解法是先逐行，再逐列的查找比较每个k*k块的杂草数，再依次进行最大值的比较。

1.由于农田是正方形的，所以行和列循环查找的次数一样，均为 n-k+1 次。

以题目中的样例为例：

2.每个k*k块的杂草数，我采用的是先加上对角线上的杂草数，再由该对角线往上和往左加上两边的杂草数。

以[1][0]坐标为当前循环开始为例：

以下为c++编写的本程序代码：

2.代码

#includeusing namespace std;int main(){int n, k;cout << "请输入n,k" <> n >> k;int len = n - k + 1;//每行每列中可以循环的次数int arry[50][50] = { 0 };//存放N*N的数据注：数组的维数大小不能过大，否则报栈不够的错误int MAX = 0;//存放最大杂草数之和cout << "请输入数组" << endl;for (int i = 0; i < n; i++){for (int j = 0; j > arry[i][j];}}for (int i = 0; i < len; i++)//每一行遍历{for (int j = 0; j  0)//算出当前k*k的值{temp = temp + arry[a][b];//先将当前位置上的杂草数加上int temp_a = a - 1;while (a > 0&&time!=k)//当前位置“往上”累加杂草{temp = temp + arry[temp_a][b];if (temp_a == i) { break; }//“往上”的上限是横纵坐标不能超过i,jtemp_a--;//使之能“往上”加的条件}int temp_b = b - 1;while (b> 0 && time != k)//当前位置“往左”累加杂草{temp = temp + arry[a][temp_b];if (temp_b == j) { break; }//“往左”的上限是横纵坐标不能超过i,jtemp_b--;//使之能“往左”加的条件}a = a + 1; b = b + 1; time = time - 1;//自左上到右下（对角线）更新当前位置}if (temp > MAX) { MAX = temp; }//比较、更新最大值}}cout << MAX << endl;return 0;}

总结

本题的算法中循环较为暴力，但以对角线累加的算法在目前使用过的其他算法中正确率高和容易理解。程序代码中的arry数组行列存储大小为50*50，这是因为编写时用的visual studio2022,维数过大，会报栈不够的错误，当然也可以修改编译器的设置，达到1000*1000的效果。

最后附带测试实例：