當(dāng)前位置:首頁 > IT技術(shù) > 編程語言 > 正文

POJ 1208 The Blocks Problem 塊問題,c++實現(xiàn)
2022-01-01 23:30:55

點擊這里訪問該問題的原鏈接。

這個問題的主要步驟是讀取操作中的信息,然后執(zhí)行相應(yīng)的操作。最重要的是如何設(shè)計數(shù)據(jù)結(jié)構(gòu)。
數(shù)據(jù)結(jié)構(gòu)的設(shè)計方法有多重多樣,這里采用了一個包含25個元素的數(shù)組(因為至多25個塊),代表25個位置,每個元素是一個vector,里面存放了該位置上面所有的塊。
這里的操作可以分解為三種,一種是找到某一個塊現(xiàn)在在什么位置,另一種是把一個位置上某一個塊上面的塊全部歸位,另一種是把一個位置上的所有塊移到另一個位置上。

(所有的指令基本就是這三種操作的組合)
所以基本上需要三個主要的函數(shù)
1. 找到某一個塊現(xiàn)在的位置,需要返回它現(xiàn)在在25個位置中的哪個位置,以及它是這個位置上從下往上數(shù)第幾個塊(也就是他的高度)。
2. 把一個位置上某一個塊上面的塊全部歸位。
3. 把一個位置上的所有塊移到另一個位置上。

對于第一個操作,可以簡單的通過遍歷得到,遍歷25個位置上的所有塊,直到某一個塊就是我們要找的塊,可以用引用類型返回它的位置和高度。
對于第二個操作,可以先找到這個塊的位置,然后把上面的所有塊歸位,然后重置這個vector的大小。
對于第三個操作,假如是A上的所有塊移到B上,可以先找到B所在的位置和A所在的位置和高度,把A高度上面的所有塊移動到B上(pushback就可以),然后重置兩個vector的大小。

基本函數(shù)實現(xiàn)后,只需要在main中循環(huán)讀取指令,分解出所需要進行的操作,然后執(zhí)行基本函數(shù)就好。

完整的代碼如下:
點擊查看代碼
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int BlockNum = 0;
vector<int> Blocks[25];

void FindBLock(int blocknum, int& blockpile, int& height) {
	for (blockpile = 0; blockpile < BlockNum; blockpile++) {
		for(height = 0;height<Blocks[blockpile].size();height++)
		{
			if (Blocks[blockpile][height] == blocknum) return;
		}
	}
}

void Homing(int blockpile,int height) {
	int i;
	int temp;
	for (i = height+1; i < Blocks[blockpile].size(); i++) {
		temp = Blocks[blockpile][i];
		Blocks[temp].push_back(temp);	}
	Blocks[blockpile].resize(height+1);
}

void moveAoverB(int blockpileA, int blockpileB, int heightA) {
	int i;
	for (i = heightA; i < Blocks[blockpileA].size(); i++) {
		Blocks[blockpileB].push_back(Blocks[blockpileA][i]);
	}
	Blocks[blockpileA].resize(heightA);
}
int main() {
	int i = 0;
	string man1, man2;
	int block1, block2;
	cin >> BlockNum;
	int pile1, pile2, height1, height2;
	while (i < BlockNum)
	{
		Blocks[i].push_back(i);
		i++;
	}
	i = 0;
	while (true)
	{
		cin >> man1;
		if (man1 != "move" && man1 != "pile") break;
		cin >> block1 >> man2 >> block2;
		FindBLock(block1, pile1, height1);
		FindBLock(block2, pile2, height2);
		if (pile1 == pile2) continue;
		if (man1 == "move") {

			Homing(pile1, height1);
		}
		if (man2 == "onto") {

			Homing(pile2, height2);
		}
		moveAoverB(pile1, pile2, height1);
	}
	for (i = 0; i < BlockNum; i++) {
		cout << i << ": ";
		for (int j = 0; j < Blocks[i].size(); j++) {
			cout <<Blocks[i][j]<<' ';
		}
		cout << endl;
	}
	return 0;
}

本文摘自 :https://www.cnblogs.com/

開通會員,享受整站包年服務(wù)立即開通 >