UVA 101: The Blocks Problem

题目链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=3&problem=37&mosmsg=Submission+received+with+ID+8686688

题目大意：

模拟机器人操作，英语不好题目容易看错，翻译如下：

机器手臂有以下几种合法的操作方式（a和b是积木的编号）：

move a onto b

在将a搬到b上之前，先将a和b上的积木放回原来的位置（例如：1就放回1的最开始位罝）

move a over b

在将a搬到b所在的那堆积木之上之前，先将a上的积木放回原来的位罝（b所在的那堆积木不动）

pile a onto b

将a本身和其上的积木一起放到b上，在搬之前b上方的积木放回原位

pile a over b

将a本身和其上的积木一起搬到b所在的那堆积木之上

quit动作结束

前四个动作中若a=b，或者a, b在同一堆积木中，那么这样的动作算是不合法的。所有不合法的动作被忽略，也就是对其个积木都不改变。

解题思路：

      一道模拟题，按着它规定的操作执行，编程相对复杂点，由于没有看对题目错了一次。

解题代码：

#include<iostream>
using namespace std;
int b[26][26];
int f[25];
int n;
void init(){
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++)
			if(j==0)
				b[i][j]=i;
			else
				b[i][j]=-1;
		f[i]=i;
	}
}
void move(string s1,int s,string s2,int d){
	if(f[s]!=f[d]){
		int i=0,j=0,fs=f[s],fd=f[d],p,q;
		while(b[fs][i]!=s)i++;
		p=i;
		if(s1=="move"){
			while(b[fs][++i]!=-1){
				b[b[fs][i]][0]=b[fs][i];
				f[b[fs][i]]=b[fs][i];
				b[fs][i]=-1;
			}
		}
		if(s2=="onto"){
			while(b[fd][j]!=d)j++;
			q=j+1;
		}
		else{
			while(b[fd][j]!=-1)j++;
			q=j;
		}
		if(s2=="onto"){
			while(b[fd][++j]!=-1){
				b[b[fd][j]][0]=b[fd][j];
				f[b[fd][j]]=b[fd][j];
				b[fd][j]=-1;
			}
		}
		i=p;j=q;
		while(b[fs][i]!=-1){
			b[fd][j++]=b[fs][i];
			f[b[fs][i]]=fd;
			b[fs][i]=-1;
			i++;
		}
	}
}
void print(){
	for(int i=0;i<n;i++){
		cout<<i<<':';
		for(int j=0;j<n;j++){
			if(b[i][j]!=-1)
				cout<<' '<<b[i][j];
			else{
				cout<<endl;
				break;
			}
		}
	}
}
int main(){
	while(cin>>n){
		string s1;
		init();
		while(cin>>s1){
			if(s1=="quit")
				break;
			int s,d;
			string s2;
			cin>>s>>s2>>d;
			move(s1,s,s2,d);
		}
		print();
	}
	return 0;
}

扩展知识：http://en.wikipedia.org/wiki/Artificial_intelligence

• 全局相关文章
• 相关文章