网站规划的任务,磁力帝,搜狐网站开发,南京公司网站建立文章目录1. 题目2. 解题1. 题目
来源#xff1a;https://tianchi.aliyun.com/oj/210874425247820050/215397455965131519
给定一个n * m 的矩阵 carrot, carrot[i][j] 表示(i, j) 坐标上的胡萝卜数量。 从矩阵的中心点出发#xff0c;每一次移动都朝着四个方向中胡萝卜数量…
文章目录1. 题目2. 解题1. 题目
来源https://tianchi.aliyun.com/oj/210874425247820050/215397455965131519
给定一个n * m 的矩阵 carrot, carrot[i][j] 表示(i, j) 坐标上的胡萝卜数量。 从矩阵的中心点出发每一次移动都朝着四个方向中胡萝卜数量最多的方向移动保证移动方向唯一。 返回你可以得到的胡萝卜数量。
示例 1:
输入:
carrot
[[5, 7, 6, 3],
[2, 4, 8, 12],
[3, 5, 10, 7],
[4, 16, 4, 17]]
输出: 83
解释起点坐标是(1, 1),
移动路线是4 - 8 - 12 - 7 - 17 - 4 - 16 - 5 - 10示例 2:
输入:
carrot
[[5, 3, 7, 1, 7],[4, 6, 5, 2, 8],[2, 1, 1, 4, 6]]输出: 30解释起始点是 (1, 2), 移动路线是 5 - 7 - 3 - 6 - 4 - 52. 解题
class Solution {
public:/*** param carrot: an integer matrix* return: Return the number of steps that can be moved.*/int PickCarrots(vectorvectorint carrot) {// write your code hereint m carrot.size(), n carrot[0].size();int x (m-1)/2, y (n-1)/2;//中心点int sum carrot[x][y];vectorvectorint dir {{0,1},{1,0},{-1,0},{0,-1}};while(true){bool exists false;int nx, ny, maxval INT_MIN, px, py;for(int k 0; k 4; k){nx x dir[k][0];ny y dir[k][1];if(nx0 nx m ny0 ny n carrot[nx][ny] ! -1){exists true;if(carrot[nx][ny] maxval){px nx, py ny;maxval carrot[nx][ny];}}}if(!exists)break;if(maxval ! INT_MIN){sum maxval;carrot[x][y] -1;//原来位置标记为走过的x px, y py;//移动到新的位置}}return sum;}
};50ms C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
