0

というわけで、 UVa Online Judgeの有名な「 The Blocks Problem」をやっています。

私のアプローチは非常にばかげています。それは、ベクトルで遊びたかったからです。そこで、各ブロックへのポインタのベクトルを山積みにして、それらのベクトルをコレクションというベクトルに格納します。

すべてのブロックを見つけるために、すべてのブロックへのポインターが内部に格納されている blockCollection というベクターがあります。

コードは提供されたサンプルに合格しています。後で編集してコメントを提供しようとします。

完全なソース:

#include <iostream>
#include <vector>

struct Block
{
    int id;
    std::vector<Block*>* where;
};

int positionInVector(Block* b);

int main(int argc, const char * argv[])
{
    std::vector<std::vector<Block*>*> collection;
    std::vector<Block*> blockCollection;
    std::string command = "", command2 = "";
    int blockCount = 0, k = 0, A = 0, B = 0;

    while ( std::cin >> blockCount )
    {
        std::vector<Block*>* vectors = new std::vector<Block*>[blockCount];
        Block* blocks = new Block[blockCount];
        for ( k = 0 ; k < blockCount ; ++ k)
        {
            blocks[k].id = k;
            blocks[k].where = &vectors[k];
            vectors[k].push_back(&blocks[k]);
            blockCollection.push_back(&blocks[k]);
            collection.push_back(&vectors[k]);
        }
        std::cin >> std::ws;
        while ( std::cin >> command )
        {
            if ( command == "quit" ) break;
            std::cin >> A >> command2 >> B;
            Block* blockA = blockCollection[A];
            Block* blockB = blockCollection[B];
            std::vector<Block*>* vectorA = blockA -> where;
            std::vector<Block*>* vectorB = blockB -> where;

            //exception handle
            if ( A > blockCount || B > blockCount ) continue;
            if ( A == B ) continue;
            if ( vectorA == vectorB ) continue;

            if ( command == "move" )
            {
                //move anything on top of A to its original position
                int positionOfBlockAInVectorA = positionInVector(blockA);
                for ( int i = positionOfBlockAInVectorA + 1 ; i < vectorA -> size() ; ++ i )
                {
                    Block* blockToBeMoved = *(vectorA -> begin() + i);
                    std::vector<Block*>* destinationVector = collection[blockToBeMoved -> id];
                    blockToBeMoved -> where = destinationVector;
                    destinationVector -> push_back(blockToBeMoved);
                }
                vectorA -> erase(vectorA -> begin() + positionOfBlockAInVectorA + 1, vectorA -> end());
            }
            if ( command2 == "onto" )
            {
                //move anything on top of B to its original position
                int positionOfBlockBInVectorB = positionInVector(blockB);
                for ( int i = positionOfBlockBInVectorB + 1 ; i < vectorB -> size() ; ++ i )
                {
                    Block* blockToBeMoved = *(vectorB -> begin() + i);
                    std::vector<Block*>* destinationVector = collection[blockToBeMoved -> id];
                    blockToBeMoved -> where = destinationVector;
                    destinationVector -> push_back(blockToBeMoved);
                }
                if (positionOfBlockBInVectorB + 1 > vectorB -> size()) vectorA -> erase(vectorB -> begin() + positionOfBlockBInVectorB + 1, vectorB -> end());
            }
            if ( command == "move" )
            {
                //move block a to the pile containing block b
                vectorA -> pop_back();
                blockA -> where = vectorB;
                vectorB -> push_back(blockA);
            }
            else
            {
                //move block a and those on top of it to the pile containing block b
                std::vector<Block*> temperaryVector;
                int positionOfBlockAInVectorA = positionInVector(blockA);
                for ( int i = (int)vectorA -> size() - 1 ; i >= positionOfBlockAInVectorA ; -- i )
                {
                    temperaryVector.push_back(vectorA -> at(i));
                    vectorA -> erase(vectorA -> begin() + i);
                }
                for ( int i = (int)temperaryVector.size() - 1 ; i >= 0 ; -- i )
                {
                    temperaryVector[i] -> where = vectorB;
                    vectorB -> push_back(temperaryVector[i]);
                }
            }
        }

        for ( k = 0 ; k < blockCount ; ++ k )
        {
            std::vector<Block*>* vector = collection[k];
            std::cout << k << ":";
            if ( !vector -> empty() )
            {
                for ( int i = 0 ; i < vector -> size() ; ++ i )
                {
                    std::cout << " " << vector -> at(i) -> id;
                }
            }
            std::cout << std::endl;
        }
        delete [] blocks;
        delete [] vectors;
    }
    return 0;
}

int positionInVector(Block* block)
{
    std::vector<Block*> vector = *block -> where;
    for ( int i = 0 ; i < vector.size() ; ++ i )
    {
        if ( vector[i] == block ) return i;
    }
    return -1;
}

ありがとう！

4

2 に答える 2

1

ブロックを blockCollection に追加または削除するたびに、コレクション内の任意のブロックに対して保持しているすべてのポインターが無効になる可能性があります。

最初に言うべきことはそれだけだと思います...

于 2013-01-22T14:25:22.423 に答える
1

これが機能するには：

        A = (int)command[5] - 48;
        B = (int)command[12] - 48;

文字列の長さが 5/12 文字で、その位置に数字があることを確認する必要があります。コードは、入力の長さとそれらの場所の数字の有効性のチェックを追加する必要があります。

于 2013-01-22T14:32:38.927 に答える