행렬 좌상단-우하단 왕복 최대 별 수집

1 개요

Maximum points from top left of matrix to bottom right and return back

행렬 좌상단-우하단 왕복 최대 별 수집

import java.util.*;
public class Solution {
	static Scanner sc = new Scanner(System.in);
	static int N, M;
	static char[][] a;
	static int[][][] dp;
	static int collect(int r1, int c1, int r2, int c2) {
		if( r1>=N || c1>=M || r2>=N || c2>=M ) return -9999;
		if(r1==r2 && c1==c2) {
			if(a[r1][c1]=='*') return 1;
			return 0;
		}
		int res = 0;
		if(a[r1][c1]=='*') res++;
		if(a[r2][c2]=='*') res++;
		return res;
	}
	static int solve(int r1, int c1, int r2) {
		int c2 = r1+c1-r2;
		if( r1==N-1 && c1==M-1 && r2==N-1 && c2==M-1) return 0;
		if( r1>=N || c1>=M || r2>=N || c2>=M ) return -9999;
		if(dp[r1][c1][r2] != -1) return dp[r1][c1][r2];
		int res = -1;
		if( c1+1<M && a[r1][c1+1] != '#') {
			if( r2+1<N && a[r2+1][c2] != '#' ) res = Math.max(res, collect(r1,c1+1,r2+1,c2)+solve(r1,c1+1,r2+1));
			if( c2+1<M && a[r2][c2+1] != '#' ) res = Math.max(res, collect(r1,c1+1,r2,c2+1)+solve(r1,c1+1,r2));
		}
		if( r1+1<N && a[r1+1][c1]!='#' ) {
			if( c2+1<M && a[r2][c2+1] != '#' ) res = Math.max(res, collect(r1+1,c1,r2,c2+1)+solve(r1+1,c1,r2));
			if( r2+1<N && a[r2+1][c2] != '#' ) res = Math.max(res, collect(r1+1,c1,r2+1,c2)+solve(r1+1,c1,r2+1));
		}
		dp[r1][c1][r2] = res;
		return dp[r1][c1][r2];
	}
	public static void main(String[] args) {
		int T = sc.nextInt();
		for(int tc=1; tc<=T; tc++) {
			N = sc.nextInt();
			M = sc.nextInt();
			a = new char[N][M];
			for(int i=0; i<N; i++) {
				a[i] = sc.next().toCharArray();
			}
			dp = new int[N][M][N];
			for(int[][] t1: dp) {
				for(int[] t2: t1) Arrays.fill(t2, -1);
			}
			int res = solve(0,0,0);
			if(a[0][0]=='*') res++;
			System.out.format("#%d %d\n", tc, res);
		}
	}
}

2 입출력

입력

3
4 4
****
.##.
.##.
****
7 9
*........
.....**#.
..**...#*
..####*#.
.*.#*.*#.
...#**...
*........
5 5
.*.*.
*###.
*.*.*
.###*
.*.*.

출력

#1 8
#2 7
#3 8

3 참고

• https://www.geeksforgeeks.org/maximum-points-top-left-matrix-bottom-right-return-back/