2169번 - 로봇 조종하기

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

public class Main {

	static int N, M;
	static int[][] map;
	static CustomCache[][] cache;
	static boolean[][] visit;
	static int IMPOSSIBLE = -20000000;
	static int NOT_TRY = -20000001;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String[] NM = br.readLine().split(" ");
		N = Integer.parseInt(NM[0]);
		M = Integer.parseInt(NM[1]);
		map = new int[N][M];
		cache = new CustomCache[N][M];
		visit = new boolean[N][M];
		for (int i = 0; i < N; i++) {
			Arrays.fill(visit[i], false);
			String[] temp = br.readLine().split(" ");
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(temp[j]);
				cache[i][j] = new CustomCache();
			}
		}
		System.out.println(travel(0, 0));
	}

	static int travel(int x, int y) {
		if (x == N - 1 && y == M - 1)
			return map[x][y];

		visit[x][y] = true;

		CustomCache now = cache[x][y];
		int ret = IMPOSSIBLE;

		// down
		if (x + 1 < N && !visit[x + 1][y]) {
			if (now.down == NOT_TRY)
				now.down = travel(x + 1, y) + map[x][y];
			ret = Math.max(ret, now.down);
		}

		// right
		if (y + 1 < M && !visit[x][y + 1]) {
			if (now.right == NOT_TRY)
				now.right = travel(x, y + 1) + map[x][y];
			ret = Math.max(ret, now.right);
		}

		// left
		if (y - 1 >= 0 && !visit[x][y - 1]) {
			if (now.left == NOT_TRY)
				now.left = travel(x, y - 1) + map[x][y];
			ret = Math.max(ret, now.left);
		}

		visit[x][y] = false;
		return ret;
	}
	static class CustomCache {
		int left = NOT_TRY;
		int right = NOT_TRY;
		int down = NOT_TRY;
	}
}