読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

UVa 101 - The Blocks Problem

UVa第一回目です。
100の3n+1は以前解いているのでまた今度。
UVaは英語なので簡単な訳と例を交えながら。

- 問題概要

BackGroundにごちゃごちゃと書いてありますが要するにブロックを扱うロボットのプログラムを作るというお話です。
ロボットは入力で与えられる4種の命令に従ってブロックの操作を行うことができる。
ブロックの数はnで入力の一番最初に与えられる。ブロックにはそれぞれ数字がついていて1,2,,n-1までの数字がついている。

  • 初期状態:

各ブロックはそれぞれ初期位置(平らな机の上)に置かれている。

例)
0: 0
1: 1
2: 2

  • move a onto b :

aとbの上に積まれているブロックを全て初期位置に戻してからaをbの上に積む

例)
0:
1: 1 0
2: 2
>move 1 onto 2
0: 0
1:
2: 2 1

  • move a over b:

aの上に積まれているブロックを全て初期位置に戻してからaをbを含むスタックの上に積む

例)
0:
1: 1 0
2: 2
>move 2 over 1
0:
1: 1 0 2
2:

:bの上に積まれているブロックを全て初期位置に戻してからaとaの上に積まれているブロック全てをbの上に積む

例)
0:
1: 1 0
2: 2 3
3:
>pile 1 onto 2
0:
1:
2: 2 1 0
3: 3

:aとaの上に積まれているブロック全てbを含むスタックの上に積む

例)
0:
1: 1 0
2: 2 3
3:
>pile 1 over 2
0:
1:
2: 2 3 1 0
3:

ここで注意点として、
1.aとbが同じ数字であるとき
2.aとbのブロックが同じスタック内に含まれるとき
はillegalなコマンドとしてその命令を無視しなければならない。実際には1を満たすときは2も満たすので2だけ確認すればよい。

(これを見落としていたためTLEが発生して10分悩まされました。)

- 解法


ブロックの最大個数が25なのでオーダーは気にしなくていいです。
ブロックを表す構造体を使って連結リストのような形で各スタックを実現しました。
struct block{
int num;
block *over,*under;
}
一つ上のブロックのポインタをoverに保持、underはなくてもいいけどあったほうが実装が楽になると思います。
それぞれの命令に対応する関数を用意して入力された命令に応じて呼び出す。ただし各関数を呼び出す前にillegalとなる命令でないか確認をする必要があるので注意。
基本的に素直に実装すればいいけどoverはポインタのをスタックの一番上に移動してからontoを呼び出せば関数が簡潔になります。

- ソースコード

#include<iostream>
#include<string>
using namespace std;
#define N 30
#define rep(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
struct block{
	int num;
	block *under, *over;
};
block blocks[N];
block pos[N];
block* top[N];
void init(int n){
	rep(i, 0, n){
		blocks[i].num = i;
		blocks[i].over = NULL;
		blocks[i].under = &(pos[i]);
		pos[i].num = -1;
		pos[i].over = &(blocks[i]);
	}
}

void output(int n){
	rep(i, 0, n){
		cout << i << ":";
		block* p = pos[i].over;
		while (p != NULL){
			cout << " " << p->num;
			p = p->over;
		}
		cout << endl;
	}
}
void reset(block* b){ 
	while (b != NULL){
		block* next = b->over;
		b->over = NULL;
		b->under = &(pos[b->num]);
		pos[b->num].over = b;
		b = next;
	}
}

void mv_onto(block* a, block* b){
	reset(a->over);
	reset(b->over);
	a->over = NULL;
	a->under->over = NULL;
	b->over = a;
	a->under = b;
}

void pile_onto(block* a, block* b){
	reset(b->over);
	a->under->over = NULL;
	b->over = a;
	a->under = b;
}

void mv_over(block* a, block *b){
	while (b->over != NULL){
		b = b->over;
	}
	mv_onto(a, b);
}
void pile_over(block* a, block *b){
	while (b->over != NULL){
		b = b->over;
	}
	pile_onto(a, b);
}

bool check(block *a, block *b){
	while (b->over != NULL){
		b = b->over;
	}
	while (a->over != NULL){
		a = a->over;
	}
	if (a == b)return false;
	else return true;
}
int main(void){
	int n,a,b;
	string str,p;
	cin >> n;
	init(n);
	while (true){
		cin >> str;
		if (str.compare("quit") == 0)
			break;
		cin >> a >> p >> b;
		if (check(blocks + a, blocks + b)){
			if (str.compare("move") == 0){
				if (p.compare("onto") == 0)
					mv_onto(blocks + a, blocks + b);
				else
					mv_over(blocks + a, blocks + b);
			}
			else{
				if (p.compare("onto") == 0)
					pile_onto(blocks + a, blocks + b);
				else
					pile_over(blocks + a, blocks + b);
			}
		}
	}
	output(n);
	return(0);
}