最多宝物

缺乏、安全感 2022-05-28 03:43 92阅读 0赞

## Problem 最多宝物    ##

Accepted: 312   Total Submit: 521  
Time Limit: 1000ms   Memony Limit: 32768KB

### Description ###

有一个 m\*n 的区域，每个小区放着一些有一定价值的宝物。第 1 行第 1 列的区域是入口，第 m 行第 n 列的区域是出口，你只能从上到下，从左到右走，请问怎样走才能获得最多的宝物。如下图：

最大的和是： 10+7+56+3+8+90+0+3=177 。

### Input ###

有多组测试用例。每组测试用例首先输入两个正整数m、n表示m\*n的区域；接着输入m行n列的整数表示m\*n的区域中含有宝物的数量。m、n为0、0时表示结束。

### Ouput ###

首先输出“Case \#m:”，m表示第几组测试用例。然后输出找到的最多的宝物数量。（详见输出样例）

### Sample Input ###

4 5  
10 7 45 -6 1  
6 56 3 8 90  
9 9 8 6 0  
8 -7 9 5 3  
3 3  
13 -1 5  
8 -3 9  
2 4 1  
4 5  
10 7 6 1 -6  
6 3 7 8 90  
9 8 6 0 6  
56 13 45 9 -3  
0 0

### Sample Output ###

Case \#1:177  
Case \#2:28  
Case \#3:145

## 分析：题目要求按2个指定方向行走到最后一个二维数组的结点，如果单纯的用递归当然也能做出来，但是这题和最大黑区域问题不一样，那么我们要用队列来处理，把2个方向都放到队列里然后通过写一个类来解决i，j还有相加的和的问题。    ##

import java.util.LinkedList;  
import java.util.Queue;  
import java.util.Scanner;  
  
public class 最多宝物 \{  
    static int dx\[\] = \{1,0\};  
    static int dy\[\] = \{0,1\};  
    public static void main(String\[\] args) \{  
        // TODO Auto-generated method stub  
        Scanner in = new Scanner(System.in);  
        int id = 1;  
        while(in.hasNext())\{  
            int n = in.nextInt();  
            int m = in.nextInt();  
            if(n==0&&m==0)  
                break;  
            int k\[\]\[\] = new int\[n\]\[m\];  
            int flag\[\]\[\] = new int\[n\]\[m\];  
            for(int i = 0;i<n;i++)\{  
                for(int j = 0;j<m;j++)\{  
                    k\[i\]\[j\] = in.nextInt();  
                \}  
            \}  
            Queue<Go> q = new LinkedList<Go>();  
            Go start = new Go(0,0,k\[0\]\[0\]);  
            Go end = new Go(n-1,m-1,k\[n-1\]\[m-1\]);  
            q.add(start);  
            int max = 0;  
            while(!q.isEmpty())\{  
                Go gg = q.poll();  
                if(gg.x==end.x&&gg.y==end.y)\{  
                    if(max<gg.value)  
                        max = gg.value;  
                \}  
                for(int i = 0;i<2;i++)\{  
                    int x = gg.x+dx\[i\];  
                    int y = gg.y+dy\[i\];  
                    if(x>=0&&x<n&&y>=0&&y<m)\{  
                        //flag\[x\]\[y\] = 1;  
                        Go g = new Go(x,y,k\[x\]\[y\]+gg.value);  
                        q.add(g);  
                    \}  
                      
                \}  
            \}  
            System.out.println("Case \#"+id+++":"+max);  
        \}  
    \}  
\}  
class Go\{  
    int x;  
    int y;  
    int value;  
    public Go(int x, int y, int value) \{  
        super();  
        this.x = x;  
        this.y = y;  
        this.value = value;  
    \}  
      
\}