보물찾기---쌍방향dp

제목 설명

전설에 의하면 HMH대사막에 M*N 미로가 있는데 그 안에 많은 보물이 숨겨져 있다고 한다.어느 날 Dr. Kong은 미로의 지도를 찾았습니다. 그는 미로 안 곳곳에 보물이 있고 가장 소중한 보물은 오른쪽 아래에 숨겨져 있고 미로의 수출입은 왼쪽 상단에 있다는 것을 발견했습니다.물론 미로 속의 통로는 평탄하지 않고 곳곳이 함정이다.Dr. Kong은 그의 로봇 카드를 탐험하러 많이 가기로 결정했다.
그러나 로봇 카도가 왼쪽 상단에서 오른쪽 하단으로 내려갈 때는 아래로 내려가거나 오른쪽으로만 간다.오른쪽 아래에서 왼쪽 상단으로 돌아갈 때는 위로 올라가거나 왼쪽으로 갈 뿐 카도는 뒤돌아보지 않는다.(즉, 한 점을 최대 한 번 통과해야 함).물론 카도르도 길을 따라 있는 보물 하나하나를 가져갔다.Dr. Kong은 그의 로봇 카드가 가능한 한 많은 보물을 가지고 나오기를 바란다.Dr. Kong이 카드가 많으면 보물을 얼마나 많이 가져올지 계산하는 데 도움을 줄 수 있도록 프로그램을 작성해 주세요.

입력

첫 번째 줄: K는 몇 개의 테스트 데이터가 있는지 나타낸다. 
다음은 각 그룹에 대한 테스트 데이터입니다.
1행: M N
2~M+1줄:Ai1 Ai2.......AiN(i=1,......m)
【제약조건】
2≤k≤5 1≤M, N≤50 0≤Aij≤100 (i=1,….,M; j=1,…,N)
모든 데이터는 정수다.데이터 사이에 공백이 하나 있다.

출력

각 그룹의 테스트 데이터에 대해 한 줄을 출력: 로봇 카드가 가장 많은 가치를 지닌 보물 수

샘플 입력

22 30 10 1010 10 80

3 30 3 92 8 55 7 100

샘플 출력

120

134

 

제목의 뜻이 명확하다. 로봇이 (1,1)점에서 (m,n)점까지 출발해서 다시 (m,n)점에서 최초점으로 돌아간다.우리는 그것을 (1,1)점에서 두 개의 로봇이 (m,n)점까지 동시에 출발하는 것으로 볼 수 있다.내가 시작한 것은 4차원이었다.f[i][j][x][y]는 로봇이 (i, j), 로봇2가 (x, y)에 있을 때 수집한 보물이 가장 많다고 밝혔다.로봇1은 위(i-1, j) 또는 왼쪽(i, j-1)에서 (i, j), 로봇2는 위(x-1, y) 또는 왼쪽(x, y-1)에서 (x, y)까지.그래서 f[i][j][x][y]=max(f[i-1][j][x-1][y], f[i-1][j][y-1], f[i][j-1][y], f[i][x-1][y], f[i][j-1][x][y-1]).이전 상태에는 네 가지 상황이 있었다.4층 순환이 필요한데 행렬이 너무 크면 초과하기 쉬워요.그러나 우리는 일부 세부 사항을 발견했다. 이렇게 하면 일부 쓸모없는 순환을 줄일 수 있다.주의: 같은 시간에 두 로봇이 걷는 걸음수는 같다. 즉, i+j=x+y이다.

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int e[55][55],dp[55][55][55][55],n,m;
int x1[4] = {0,0,1,1}, y1[4] = {1,1,0,0}, x2[4]={0,1,0,1}, y2[4] = {1,0,1,0};
void dp1(){
	int i,j,x,y;
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			for(x=1;x<=i;x++){
				for(y=1;y<=m;y++){
					if(i==x&&j==y) continue;
					if((i+j)!=(x+y)) continue;
					for(int k=0;k<4;k++){
						int sum=e[i][j]+e[x][y];
						dp[i][j][x][y]=max(dp[i][j][x][y],dp[i-x1[k]][j-y1[k]][x-x2[k]][y-y2[k]]+sum);
					}
				}
			}
		}
	}
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);
		memset(dp,0,sizeof(dp));
		memset(e,0,sizeof(e));
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				scanf("%d",&e[i][j]);
			}
		}
		dp1();
		printf("%d
",dp[n][m-1][n-1][m]+e[n][m]);
	}
	return 0;
}