UVA 12825 dp
#include <iostream>
#include <stdio.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <queue>
using namespace std ;
const int inf = 100000000 ;
const int N = 1008 ;
int dxmin[N][4] ;
int dxmax[N][4] ;
int dymin[N][4] ;
int dymax[N][4] ;
char d[N] ;
int n ;
int dx[4] = {1,0,-1,0} ;
int dy[4] = {0,-1,0,1} ;
char word[N] ;
int main()
{
//freopen("a.txt" , "r" , stdin) ;
int ca = 1 ;
while(scanf("%s" , word+1) != EOF){
n = strlen(word+1) ;
for(int i = 0 ; i <= n ; i++){
for(int j = 0 ; j < 4 ; j++){
dxmin[i][j] = dxmax[i][j] = dymin[i][j] = dymax[i][j] = inf ;
}
}
dxmin[0][0] = 0 ;
dxmax[0][0] = 0 ;
dymin[0][0] = 0 ;
dymax[0][0] = 0 ;
for(int i = 1 ; i <= n ; i++){
if(word[i] == 'F'){
for(int j = 0 ; j < 4 ; j++){
if(dxmin[i-1][j] != inf)
if(dxmin[i][j] == inf) dxmin[i][j] = dxmin[i-1][j] + dx[j] ;
else dxmin[i][j] = std::min(dxmin[i][j] , dxmin[i-1][j] + dx[j]) ;
}
for(int j = 0 ; j < 4 ; j++){
if(dxmax[i-1][j] != inf)
if(dxmax[i][j] == inf) dxmax[i][j] = dxmax[i-1][j] + dx[j] ;
else dxmax[i][j] = std::max(dxmax[i][j] , dxmax[i-1][j] + dx[j]) ;
}
for(int j = 0 ; j < 4 ; j++){
if(dymin[i-1][j] != inf)
if(dymin[i][j] == inf) dymin[i][j] = dymin[i-1][j] + dy[j] ;
else dymin[i][j] = std::min(dymin[i][j] , dymin[i-1][j] + dy[j]) ;
}
for(int j = 0 ; j < 4 ; j++){
if(dymax[i-1][j] != inf)
if(dymax[i][j] == inf) dymax[i][j] = dymax[i-1][j] + dy[j] ;
else dymax[i][j] = std::max(dymax[i][j] , dymax[i-1][j] + dy[j]) ;
}
}
else if(word[i] == 'L'){
for(int j = 0 ; j < 4 ; j++){
if(dxmin[i-1][(j+1)%4] != inf)
if(dxmin[i][j] == inf) dxmin[i][j] = dxmin[i-1][(j+1)%4] ;
else dxmin[i][j] = std::min(dxmin[i][j] , dxmin[i-1][(j+1)%4]) ;
}
for(int j = 0 ; j < 4 ; j++){
if(dxmax[i-1][(j+1)%4] != inf)
if(dxmax[i][j] == inf) dxmax[i][j] = dxmax[i-1][(j+1)%4] ;
else dxmax[i][j] = std::max(dxmax[i][j] , dxmax[i-1][(j+1)%4]) ;
}
for(int j = 0 ; j < 4 ; j++){
if(dymin[i-1][(j+1)%4] != inf)
if(dymin[i][j] == inf) dymin[i][j] = dymin[i-1][(j+1)%4] ;
else dymin[i][j] = std::min(dymin[i][j] , dymin[i-1][(j+1)%4]) ;
}
for(int j = 0 ; j < 4 ; j++){
if(dymax[i-1][(j+1)%4] != inf)
if(dymax[i][j] == inf) dymax[i][j] = dymax[i-1][(j+1)%4] ;
else dymax[i][j] = std::max(dymax[i][j] , dymax[i-1][(j+1)%4]) ;
}
}
else if(word[i] == 'R'){
for(int j = 0 ; j < 4 ; j++){
if(dxmin[i-1][(j-1+4)%4] != inf)
if(dxmin[i][j] == inf) dxmin[i][j] = dxmin[i-1][(j-1+4)%4] ;
else dxmin[i][j] = std::min(dxmin[i][j] , dxmin[i-1][(j-1+4)%4]) ;
}
for(int j = 0 ; j < 4 ; j++){
if(dxmax[i-1][(j-1+4)%4] != inf)
if(dxmax[i][j] == inf) dxmax[i][j] = dxmax[i-1][(j-1+4)%4] ;
else dxmax[i][j] = std::max(dxmax[i][j] , dxmax[i-1][(j-1+4)%4]) ;
}
for(int j = 0 ; j < 4 ; j++){
if(dymin[i-1][(j-1+4)%4] != inf)
if(dymin[i][j] == inf) dymin[i][j] = dymin[i-1][(j-1+4)%4] ;
else dymin[i][j] = std::min(dymin[i][j] , dymin[i-1][(j-1+4)%4]) ;
}
for(int j = 0 ; j < 4 ; j++){
if(dymax[i-1][(j-1+4)%4] != inf)
if(dymax[i][j] == inf) dymax[i][j] = dymax[i-1][(j-1+4)%4] ;
else dymax[i][j] = std::max(dymax[i][j] , dymax[i-1][(j-1+4)%4]) ;
}
}
else{
for(int j = 0 ; j < 4 ; j++){
if(dxmin[i-1][j] != inf)
if(dxmin[i][j] == inf) dxmin[i][j] = dxmin[i-1][j] + dx[j] ;
else dxmin[i][j] = std::min(dxmin[i][j] , dxmin[i-1][j] + dx[j]) ;
}
for(int j = 0 ; j < 4 ; j++){
if(dxmax[i-1][j] != inf)
if(dxmax[i][j] == inf) dxmax[i][j] = dxmax[i-1][j] + dx[j] ;
else dxmax[i][j] = std::max(dxmax[i][j] , dxmax[i-1][j] + dx[j]) ;
}
for(int j = 0 ; j < 4 ; j++){
if(dymin[i-1][j] != inf)
if(dymin[i][j] == inf) dymin[i][j] = dymin[i-1][j] + dy[j] ;
else dymin[i][j] = std::min(dymin[i][j] , dymin[i-1][j] + dy[j]) ;
}
for(int j = 0 ; j < 4 ; j++){
if(dymax[i-1][j] != inf)
if(dymax[i][j] == inf) dymax[i][j] = dymax[i-1][j] + dy[j] ;
else dymax[i][j] = std::max(dymax[i][j] , dymax[i-1][j] + dy[j]) ;
}
for(int j = 0 ; j < 4 ; j++){
if(dxmin[i-1][(j+1)%4] != inf)
if(dxmin[i][j] == inf) dxmin[i][j] = dxmin[i-1][(j+1)%4] ;
else dxmin[i][j] = std::min(dxmin[i][j] , dxmin[i-1][(j+1)%4]) ;
}
for(int j = 0 ; j < 4 ; j++){
if(dxmax[i-1][(j+1)%4] != inf)
if(dxmax[i][j] == inf) dxmax[i][j] = dxmax[i-1][(j+1)%4] ;
else dxmax[i][j] = std::max(dxmax[i][j] , dxmax[i-1][(j+1)%4]) ;
}
for(int j = 0 ; j < 4 ; j++){
if(dymin[i-1][(j+1)%4] != inf)
if(dymin[i][j] == inf) dymin[i][j] = dymin[i-1][(j+1)%4] ;
else dymin[i][j] = std::min(dymin[i][j] , dymin[i-1][(j+1)%4]) ;
}
for(int j = 0 ; j < 4 ; j++){
if(dymax[i-1][(j+1)%4] != inf)
if(dymax[i][j] == inf) dymax[i][j] = dymax[i-1][(j+1)%4] ;
else dymax[i][j] = std::max(dymax[i][j] , dymax[i-1][(j+1)%4]) ;
}
for(int j = 0 ; j < 4 ; j++){
if(dxmin[i-1][(j-1+4)%4] != inf)
if(dxmin[i][j] == inf) dxmin[i][j] = dxmin[i-1][(j-1+4)%4] ;
else dxmin[i][j] = std::min(dxmin[i][j] , dxmin[i-1][(j-1+4)%4]) ;
}
for(int j = 0 ; j < 4 ; j++){
if(dxmax[i-1][(j-1+4)%4] != inf)
if(dxmax[i][j] == inf) dxmax[i][j] = dxmax[i-1][(j-1+4)%4] ;
else dxmax[i][j] = std::max(dxmax[i][j] , dxmax[i-1][(j-1+4)%4]) ;
}
for(int j = 0 ; j < 4 ; j++){
if(dymin[i-1][(j-1+4)%4] != inf)
if(dymin[i][j] == inf) dymin[i][j] = dymin[i-1][(j-1+4)%4] ;
else dymin[i][j] = std::min(dymin[i][j] , dymin[i-1][(j-1+4)%4]) ;
}
for(int j = 0 ; j < 4 ; j++){
if(dymax[i-1][(j-1+4)%4] != inf)
if(dymax[i][j] == inf) dymax[i][j] = dymax[i-1][(j-1+4)%4] ;
else dymax[i][j] = std::max(dymax[i][j] , dymax[i-1][(j-1+4)%4]) ;
}
}
}
int xmin = inf ;
for(int i = 0 ; i < 4 ; i++){
if(dxmin[n][i] != inf) xmin = std::min(xmin , dxmin[n][i]) ;
}
int xmax = -inf ;
for(int i = 0 ; i < 4 ; i++){
if(dxmax[n][i] != inf) xmax = std::max(xmax , dxmax[n][i]) ;
}
int ymin = inf ;
for(int i = 0 ; i < 4 ; i++){
if(dymin[n][i] != inf) ymin = std::min(ymin , dymin[n][i]) ;
}
int ymax = -inf ;
for(int i = 0 ; i < 4 ; i++){
if(dymax[n][i] != inf) ymax = std::max(ymax , dymax[n][i]) ;
}
printf("Case %d: %d %d %d %d
" , ca++ , xmin , xmax , ymin , ymax) ;
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
