リンク先問題。
できるだけ自分の実力で解きたかったのですが、何度もテストデータで不正解の判定をくらってしまいます。
何が悪かったのか、ポカミスがないか、それとも考え違いか。
どなたかアドバイスをお願いします。
#include <stdio.h>
#include <algorithm>
void upDown(int *bill,int *moves,int n);
void solve(int n);
int moves1[105],moves2[105];
int b1[105],b2[105];
int myMax=1000000000;
int main(){
int n;
scanf("%d",&n);
while(n!=0){
solve(n);
scanf("%d",&n);
}
}
void solve(int n){
//ビルデータの読み込み
for(int i=0;i<n;i++){
scanf("%d",&b1[i]);
}
for(int i=0;i<n;i++){
scanf("%d",&b2[i]);
moves1[i]=moves2[i]=myMax;
}
moves1[0]=moves2[0]=0;
upDown(b1,moves1,n);
upDown(b2,moves2,n);
int myMaxCount=1;
//ダイクストラ法の応用で解く、一階を0とし一階に梯子があればそれを上る。未踏もしくは梯子の先頭以外、滑る壁はmyMaxに設定
while(myMaxCount>0 || myMax>moves1[n-1] || myMax>moves2[n-1]){
if(myMax>moves1[n-1] || myMax>moves2[n-1]){
printf("%d\n",std::min(moves1[n-1],moves2[n-1]));
return ;
}
myMaxCount=0;
for(int i=0;i<n;i++){
if(moves1[i]==myMax)myMaxCount++;
if(moves2[i]==myMax)myMaxCount++;
}
for(int i=0;i<n;i++){
if(myMax>moves1[i]){
int t=moves1[i]+1;
moves2[i ]=std::min(t,moves2[i ]);
moves2[i+1]=std::min(t,moves2[i+1]);
moves2[i+2]=std::min(t,moves2[i+2]);
}
}
upDown(b2,moves2,n);
for(int i=0;i<n;i++){
if(myMax>moves2[i]){
int t=moves2[i]+1;
moves1[i ]=std::min(t,moves1[i ]);
moves1[i+1]=std::min(t,moves1[i+1]);
moves1[i+2]=std::min(t,moves1[i+2]);
}
}
upDown(b1,moves1,n);
for(int i=0;i<n;i++){
if(moves1[i]==myMax)myMaxCount--;
if(moves2[i]==myMax)myMaxCount--;
}
}
printf("NA\n");
return ;
}
void upDown(int *bill,int *moves,int n){
bool upFlag=false;
int upMin;
//梯子を上る処理
for(int i=0;i<n;i++){
if(bill[i]==1 && myMax>moves[i] && upFlag==false){
upMin=moves[i];
moves[i]=myMax;
upFlag=true;
}else if(bill[i]!=1 && upFlag==true){
upFlag=false;
moves[i-1]=upMin;
}else if(i==n-1 && upFlag==true){
moves[i]=std::min(upMin,moves[i]);
break ;
}
if(upFlag==true){
upMin=std::min(upMin,moves[i]);
moves[i]=myMax;
}
}
bool downFlag=false;
int downMin;
//滑り降りる処理
for(int i=n-1;i>=0;i--){
if(bill[i]==2 && myMax>moves[i] && downFlag==false){
downMin=moves[i];
downFlag=true;
moves[i]=myMax;
}else if(bill[i]!=2 && downFlag==true){
moves[i]=std::min(downMin,moves[i]);
downFlag=false;
}else if(i==0 && downFlag==true){
moves[0]=0;
break ;
}
if(downFlag==true){
downMin=std::min(downMin,moves[i]);
moves[i]=myMax;
}
}
}