coin

• Coin-collecting by robot
  • 题目描述
  • 输入
  • 输出
  • 样例输入
  • 样例输出
  • 题目大意
  • 代码
  • 结果

Coin-collecting by robot

题目描述

Several coins are placed in cells of an n×m board. A robot, located in the upper left cell of the board, needs to collect as many of the coins as possible and bring them to the bottom right cell. On each step, the robot can move either one cell to the right or one cell down from its current location.

输入

1
2

The fist line is n,m, which 1< = n,m <= 1000.
Then, have n row and m col, which has a coin in cell, the cell number is 1, otherwise is 0.

输出

1

The max number Coin-collecting by robot.

样例输入

1
2
3
4
5
6

5 6
0 0 0 0 1 0 
0 1 0 1 0 0 
0 0 0 1 0 1 
0 0 1 0 0 1 
1 0 0 0 1 0

样例输出

1

5

题目大意

一个n行m列的单元区域内，从左上角的单元开始，只能向右/向下移动一个单元格，求出从左上角到右下角途中收集到的1的最大数量。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

using namespace std;


int e[1001][1001]={0}; 
void (int m,int n){
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			if(e[i-1][j]>e[i][j-1]){
				 
				e[i][j]+=e[i-1][j];
			}else{
				
				e[i][j]+=e[i][j-1];
			}
		}
	}
	//直接输出右下角的内容即可 
	cout<<e[m][n]<<endl;
}
int main(){
	int m,n;
	cin>>m>>n;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			cin>>e[i][j];
		}
	}
	//直接调用函数即可 
	solve(m,n);
	return 0;
}

结果