백준 10251 운전 면허 시험

https://www.acmicpc.net/problem/10251

DP 문제입니다. 시간은 방향을 바꾸는 횟수에 비례하므로 범위를 N+M이하로 줄일 수 있습니다.(time=(n+m-2) * l+turn)

memo[x][y][turn] 배열에는 최소 가스 양을 저장합니다. turn만큼만 방향을 바꾸어서 도착할 수 없거나 보유한 가스보다 최소 가스가 더 클 경우에는 도착지에 도착할 수 없습니다.

코드를 보죠!

 #include<bits/stdc++.h>
using namespace std;
const int SZ=105;
const int INF=20000005;
int memo[SZ][SZ][SZ][2];
int graph[SZ][SZ];
int left_w[SZ][SZ];
int down_w[SZ][SZ];
int n,m,l,g;
int min_gas(int x, int y, int ch, int dir){	// 0 is left, 1 is down
	if(ch<0) return INF;
	if(memo[x][y][ch][dir]!=-1) return memo[x][y][ch][dir];
	if(x==1 && y==1) return 0;
	int tmp=INF;
	if(dir==0 && y>1){
		tmp=min(min_gas(x,y-1,ch,0),min_gas(x,y-1,ch-1,1))+left_w[x][y-1];
	}
	else if(dir==1 && x>1){
		tmp=min(min_gas(x-1,y,ch-1,0),min_gas(x-1,y,ch,1))+down_w[x-1][y];
	}
	return memo[x][y][ch][dir]=tmp>INF? INF:tmp;
}
int main(void){
	ios::sync_with_stdio(false); cin.tie(NULL);
	int t; cin>>t;
	while(t--){
		cin>>n>>m>>l>>g;
		memset(memo,-1,sizeof(memo));
		for(int i=1;i<=n;i++){
			for(int j=1;j<m;j++) cin>>left_w[i][j];
		}
		for(int i=1;i<n;i++){
			for(int j=1;j<=m;j++) cin>>down_w[i][j];
		}
		int ans=INF;
		for(int i=1;i<=n+m;i++){
			if(min_gas(n,m,i,0)<=g || min_gas(n,m,i,1)<=g){
				ans=(n+m-2)*l+i;
				break;
			}
		}
		if(ans<INF) cout<<ans<<'\n';
		else cout<<-1<<'\n';
	}
	return 0;
}