最多宝物

本文主要是介绍最多宝物，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem 最多宝物

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

Description

Input

Ouput

Sample Input

Sample Output

分析：题目要求按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;
    }
    
}

这篇关于最多宝物的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---