boj-11048

gistfile1.txt

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * https://www.acmicpc.net/problem/11048
 */
public class Main {
    private static int[][] maze;
    private static long max=0;
    private static int height;
    private static int width;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] sizeStr = br.readLine().split(" ");
        height = Integer.parseInt(sizeStr[0]);
        width = Integer.parseInt(sizeStr[1]);
        maze = new int[height+1][width+1];
        boolean[][] visited = new boolean[height+1][width+1];

        for(int i=1;i<=height;i++){
            String[] candies = br.readLine().split(" ");
            for(int j=1;j<=width;j++){
                maze[i][j] = Integer.parseInt(candies[j-1]);
            }
        }
        move(visited, 0, 1,1);
        System.out.println(max);

    }

    private static int move(boolean[][] visited, long sum, int i, int j){
        if(i == height && j == width){
            sum += maze[i][j];
            if(sum > max){
                max = sum;
            }
            return 0;
        }
        if(i <= height && j <= width && !visited[i][j]){
            visited[i][j] = true;
            sum += maze[i][j];
            move(visited, sum, i+1, j);
            move(visited, sum, i, j+1);
            move(visited, sum, i+1, j+1);
        }
        return 0;
    }
}