「2011年３月」の編集履歴（バックアップ）一覧に戻る
2011年３月 - (2011/03/03 (木) 18:23:53) のソース
*2011/3/3
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0230&lang=jp
リンク先を解くコード。
意外と例外処理が多いのでめんどくさい。
記述ミスがないか怖いなあ。
#include <stdio.h>
#include <algorithm>
int b1[104],b2[104];
int moves1[104],moves2[104];//0なら未踏、1以上ならそこからジャンプ、-1なら滑り降りか上りでジャンプではない
int jumpCount;
int newJumpCount;
int main()
{
int n;
scanf("%d",&n);
while(n>0)
{
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]=0;
}
for(int i=0;i<3;i++){
moves1[i]=moves2[i]=1;
}
upDown(b1,moves1,n);
upDown(b2,moves2,n);
newJumpCount=1//ジャンプで新しい地点に到達したらインクリメント、これが0のままなら永遠にたどり着けない
while(newjumpCount>0){
newjumpCount=0;
if(moves1[n-1]>0 || moves2[n-1]>0){
printf("%d\n",std::min(moves1[n-1],moves2[n-1]));
return;
}
for(int i=0;i<n;i++){
if(moves1[i]>0){
if(moves2[i]==0 || moves2[i+1]==0 || moves2[i+2]==0){
newjumpCount++;
}
moves2[i]=myMin(moves1[i]+1,moves2[i]);
moves2[i+1]=myMin(moves1[i]+1,moves2[i+1]);
moves2[i+2]=myMin(moves1[i]+1,moves2[i+2]);
}
}
upDown(b2,moves2,n);
for(int i=0;i<n;i++){
if(moves2[i]>0){
if(moves1[i]==0 || moves1[i+1]==0 || moves1[i]==0){
newjumpCount++;
}
moves1[i]=myMin(moves2[i]+1,moves1[i]);
moves1[i+1]=myMin(moves2[i]+1,moves1[i+1]);
moves1[i+2]=myMin(moves2[i]+1,moves1[i+2]);
}
}
upDown(b1,moves1,n);
}
printf("NA\n");
return ;
}
int myMin(int a,int b){
if(b>0){
return std::min(a,b)
}else{
return a;
}
}
void upDown(int *b,int *moves,int n){
//梯子を上る処理
bool upOK=false;
int upMin;
for(int i=0;i<n;i++){
if(b[i]==1 && moves[i]>0 && upOK==false){
upOK=true;
upMin=moves[i];
moves[i]=-1;
}else if(b[i]!=1 && upOK==true){
moves[i-1]=myMin(upMin,moves[i-1]);
upOK=false;
}
if(upOK==true && moves[i]>0){
upMin=std::min(upMin,moves[i]);
moves[i]=-1;
}
}
//滑り降りる処理
bool downOK=false;
int downMin;
for(int i=n;i>0;i--){
if(b[i]==2 && moves[i]>0 && downOK==false){
moves[i]=-1;
downMin=moves[i];
downOK=true
}else if(b[i]!=2 && downOK==true){
moves[i]=myMin(downMin,moves[i]);
downOK=false;
}
if(downOK==true && moves[i]>0){
downMin=std::min(downMin,moves[i]);
moves[i]=-1;
}
}
}
*2011/3/2
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0230&lang=jp
を解くコード。
うーん、そのまま実装すればいいんだけど、探索だと計算量がおかしなことになる。
メモカ探索だな。
#include <stdio.h>
int b1[101],b2[101];
bool moveOKs1[101],moveOKs2[101];//左右のビルで一度通った場所を２度とおるなら永遠に登れない
int main()
{
int n;
scanf("%d",&n);
while(n>0)
{
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]);
}
*2011/3/2
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0179
を解くコードなのだけど、なぜかテストデータを通らない？
何かポカミスでもあったかな？
変数の初期化忘れだった。
まだまだ高校生レベルプログラムの世界。
もう少し精進しないと。
プログラムの腕を磨いてお金を稼いで、阿部大和ちゃんをお嫁さんにしてかわいい赤ちゃんをまいにち抱っこするような生活送りたいなあ。
#include <stdio.h>
#include <string.h>
#include <set>
#include <string>
void search();
std::string changeColor(std::string worm,int p);
std::string s1;
std::set<std::string> worms;//一度通った色を覚える
std::set<std::string> nows;//ｎターン目の虫の色たち
std::set<std::string> nexts;//次の虫の色たち
std::set<std::string>::iterator it;
char cWorm[11];
int minTime;
int n;
int timeMax=1000000000;
int main(){
scanf("%s",cWorm);
n=strlen(cWorm);
while(cWorm[0]!='0' && n>1){
minTime=0;
worms.clear();
nows.clear();
nexts.clear();
search();
if(minTime==timeMax){
printf("NA\n");
}else{
printf("%d\n",minTime);
}
scanf("%s",cWorm);
n=strlen(cWorm);
}
}
int rgbCount(std::string cWorm){
int colorCount=0;//同色のカウント
char t=cWorm[0];
for(int i=0;i<n;i++){
if(t==cWorm[i]) colorCount++;
else break;
}
return colorCount;
}
void search(){
//幅優先探索で検索する。
//3＾10≒60000なので何とかなる
nows.insert(cWorm);
worms.insert(cWorm);
if(rgbCount(std::string(cWorm))==n){minTime=0; return;}
std::string worm,nextWorm;
int changeCount=1;
while(changeCount>0){
minTime++;
changeCount=0;
it=nows.begin();
nexts.clear();
while(it!=nows.end()){
worm=(*it);
for(int i=0;i<n-1;i++){
if(worm[i]!=worm[i+1]){
nextWorm=changeColor(worm,i);
if(worms.find(nextWorm)==worms.end()){
worms.insert(nextWorm);
nexts.insert(nextWorm);
changeCount++;
if(rgbCount(nextWorm)==n) return;
}
}
}
it++;
}
nows.clear();
it=nexts.begin();
while(it!=nexts.end()){
nows.insert(*it);
it++;
}
}
minTime=timeMax;
return ;
}
std::string changeColor(std::string worm,int p){
char t1,t2,t3;
std::string nextworm=worm;
t1=worm[p];
t2=worm[p+1];
if((t1=='r' && t2=='g') || (t1=='g' && t2=='r')){
nextworm[p]=nextworm[p+1]='b';
}else if((t1=='r' && t2=='b') || (t1=='b' && t2=='r')){
nextworm[p]=nextworm[p+1]='g';
}else if((t1=='g' && t2=='b') || (t1=='b' && t2=='g')){
nextworm[p]=nextworm[p+1]='r';
}
return nextworm;
}
*2011/3/1
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0200&lang=jp
を解くコード。
なのだがテストコードに通すの怖い。
初期化忘れとか、、、怖い。
チェックしてから投稿することにしよう。
#include <stdio.h>
#include <map>
void setmap(int n,int m);
void searchMapCost(int s,int g,int m,std::map<int,int> *map);
std::map<int,int> costMap[101];
std::map<int,int> timeMap[101];
std::map<int,int>::iterator nextHome;
bool moveOKs[101];
int costs[101];
int mymax=1000000000;
int main(void)
{
int n,m;
scanf("%d %d",&n,&m);
while(n!=0 || m!=0){
setmap(n,m);
scanf("%d %d",&n,&m);
}
}
void setmap(int n,int m){
for(int i=1;i<=m;i++){
costMap[i].clear();
timeMap[i].clear();
}
int a,b,cost,time;
for(int i=0;i<n;i++)
{
scanf("%d %d %d %d",&a,&b,&cost,&time);
costMap[a][b]=cost;
costMap[b][a]=cost;
timeMap[a][b]=time;
timeMap[b][a]=time;
}
int k;
scanf("%d",&k);
int p,q,r;
for(int i=0;i<k;i++)
{
scanf("%d %d %d",&p,&q,&r);
if(r==0){
searchMapCost(p,q,m,costMap);
}else if(r==1){
searchMapCost(p,q,m,timeMap);
}
}
}
void searchMapCost(int s,int g,int m,std::map<int,int> *map){
for(int i=1;i<=m;i++){
costs[i]=mymax;
moveOKs[i]=true;
}
costs[s]=0;
int min=mymax;
int p;
int key,v;
for(int k=0;k<m+1;k++)
{
min=mymax;
for(int i=1;i<=m;i++){
if(costs[i]<min && moveOKs[i]==true){
min=costs[i];
p=i;
}
}
if(min==mymax) break;
moveOKs[p]=false;
nextHome=map[p].begin();
while(nextHome!=map[p].end()){
key=(*nextHome).first;
v=(*nextHome).second;
if(costs[p]+v<costs[key]) costs[key]=costs[p]+v;
nextHome++;
}
}
printf("%d\n",costs[g]);
}
