1

我需要在网格中放置数字，使其不会相互碰撞。这个数字的位置应该是随机的，可以是水平的或垂直的。这些数字基本上表明了船只的位置。所以船的点应该是在一起的，需要是随机的，不应该发生碰撞。

我试过了：

int main()
{
    srand(time(NULL));
    int Grid[64];
    int battleShips;
    bool battleShipFilled;

    for(int i = 0; i < 64; i++)
        Grid[i]=0;

    for(int i = 1; i <= 5; i++)
    {
        battleShips = 1;
        while(battleShips != 5)
        {
            int horizontal = rand()%2;
            if(horizontal == 0)
            {
                battleShipFilled = false;
                while(!battleShipFilled)
                {
                    int row = rand()%8;
                    int column = rand()%8;

                    while(Grid[(row)*8+(column)] == 1)
                    {
                        row = rand()%8;
                        column = rand()%8;
                    }

                    int j = 0;
                    if(i == 1) j= (i+1);
                    else j= i;

                    for(int k = -j/2; k <= j/2; k++)
                    {
                        int numberOfCorrectLocation = 0;
                        while(numberOfCorrectLocation != j)
                        {
                            if(row+k> 0 && row+k<8)
                            {
                                if(Grid[(row+k)*8+(column)] == 1) break;
                                numberOfCorrectLocation++;
                            }
                        }
                        if(numberOfCorrectLocation !=i) break;
                    }

                    for(int k = -j/2; k <= j/2; k++)
                        Grid[(row+k)*8+(column)] = 1;
                    battleShipFilled = true;    
                }
                battleShips++;
            }
            else
            {
                battleShipFilled = false;
                while(!battleShipFilled)
                {
                    int row = rand()%8;
                    int column = rand()%8;

                    while(Grid[(row)*8+(column)] == 1)
                    {
                        row = rand()%8;
                        column = rand()%8;
                    }

                    int j = 0;
                    if(i == 1) j= (i+1);
                    else j= i;

                    for(int k = -j/2; k <= j/2; k++)
                    {
                        int numberOfCorrectLocation = 0;
                        while(numberOfCorrectLocation != i)
                        {
                            if(row+k> 0 && row+k<8)
                            {
                                if(Grid[(row)*8+(column+k)] == 1) break;
                                numberOfCorrectLocation++;
                            }
                        }
                        if(numberOfCorrectLocation !=i) break;
                    }

                    for(int k = -j/2; k <= j/2; k++)
                        Grid[(row)*8+(column+k)] = 1;
                    battleShipFilled = true;    
                }
                battleShips++;
            }
        }
    }
}

但是我编写的代码无法在 8x8 网格中随机生成数字。

需要一些有关如何解决此问题的指导。如果有更好的方法，请告诉我...

它应该看起来如何：

在此处输入图像描述

我的代码在做什么：基本上，我在网格上放置了 5 艘不同大小的船。对于每一个，我都会检查是否要随机放置它水平或垂直。之后，我检查周围是否已填满。如果没有，我把它们放在那里。或者我重复这个过程。

要点：我只需要使用while，for循环..

4

4 回答 4

1

你最好使用递归来解决这个问题。这将为您的算法提供展开的可能性。我的意思是你可以部署每艘船并将下一部分放置在船的随机末端，然后检查新放置的船部分是否有相邻的瓷砖空并前进到下一个。如果碰巧碰到另一艘船，由于递归性质，它将移除放置的瓷砖并在另一端尝试。如果船舶的位置无效，则应将船舶放置在不同的位置并重新开始。

我在一个单词搜索游戏中使用了这个解决方案，其中必须在棋盘上填充要查找的单词。工作完美。

这是我的单词搜索游戏中的代码：

bool generate ( std::string word, BuzzLevel  &level, CCPoint position, std::vector<CCPoint> &placed, CCSize lSize )
{
    std::string cPiece;

    if ( word.size() == 0 ) return true;
    if ( !level.inBounds ( position ) ) return false;
    cPiece += level.getPiece(position)->getLetter();
    int l = cPiece.size();
    if ( (cPiece != " ") && (word[0] != cPiece[0]) ) return false;
    if ( pointInVec (position, placed) ) return false;
    if ( position.x >= lSize.width || position.y >= lSize.height || position.x < 0 || position.y < 0 ) return false;

    placed.push_back(position);

    bool used[6];
    for ( int t = 0; t < 6; t++ ) used[t] = false;

    int adj;
    while ( (adj = HexCoord::getRandomAdjacentUnique(used)) != -1 )
    {
    CCPoint nextPosition = HexCoord::getAdjacentGridPositionInDirection((eDirection) adj, position);

    if ( generate ( word.substr(1, word.size()), level, nextPosition, placed, lSize ) ) return true;

}

    placed.pop_back();
    return false;    
}

CCPoint getRandPoint ( CCSize size )
{
    return CCPoint ( rand() % (int)size.width, rand() % (int)size.height);
}


void generateWholeLevel ( BuzzLevel &level,
                                   blockInfo* info,
                                   const CCSize &levelSize, 
                                   vector<CCLabelBMFont*> wordList
                                   )
{
    for ( vector<CCLabelBMFont*>::iterator iter = wordList.begin();
         iter != wordList.end(); iter++ )
    {
        std::string cWord = (*iter)->getString();
       // CCLog("Curront word %s", cWord.c_str() );
        vector<CCPoint> wordPositions;

        int iterations = 0;
        while ( true )
        {
            iterations++;
            //CCLog("iteration %i", iterations );
            CCPoint cPoint = getRandPoint(levelSize);
            if ( generate (cWord, level, cPoint, wordPositions, levelSize ) )
            {
                //Place pieces here
                for ( int t = 0; t < cWord.size(); t++ )
                {
                    level.getPiece(wordPositions[t])->addLetter(cWord[t]);
                }
                break;
            }

            if ( iterations > 1500 )
            {
                level.clear();
                generateWholeLevel(level, info, levelSize, wordList);
                return;
            }
        }
    }
}

我可能会补充说，游戏中使用的形状是蜂窝。字母可以向任何方向缠绕，所以上面的代码比我猜你要找的要复杂得多，但会提供一个起点。

回到家后我会提供更合适的东西，因为我现在没有足够的时间。

于 2013-08-20T21:09:36.587 回答
1

一个非常快速且可能有问题的示例，说明如何通过使用一些 OOP 来真正清理解决方案并使其更加灵活：

enum Orientation {
    Horizontal,
    Vertical
};

struct Ship {
    Ship(unsigned l = 1, bool o = Horizontal) : length(l), orientation(o) {}
    unsigned char length;
    bool orientation;
};

class Grid {
public:
    Grid(const unsigned w = 8, const unsigned h = 8) : _w(w), _h(h) {
        grid.resize(w * h);
        foreach (Ship * sp, grid) {
            sp = nullptr;
        }
    }

    bool addShip(Ship * s, unsigned x, unsigned y) {
        if ((x <= _w) && (y <= _h)) { // if in valid range
            if (s->orientation == Horizontal) {
                if ((x + s->length) <= _w) { // if not too big
                    int p = 0; //check if occupied
                    for (int c1 = 0; c1 < s->length; ++c1) if (grid[y * _w + x + p++]) return false;
                    p = 0; // occupy if not
                    for (int c1 = 0; c1 < s->length; ++c1)  grid[y * _w + x + p++] = s;
                    return true;
                } else return false;
            } else {
                if ((y + s->length) <= _h) {
                    int p = 0; // check
                    for (int c1 = 0; c1 < s->length; ++c1) {
                        if (grid[y * _w + x + p]) return false;
                        p += _w;
                    }
                    p = 0; // occupy
                    for (int c1 = 0; c1 < s->length; ++c1) {
                        grid[y * _w + x + p] = s;
                        p += _w;
                    }
                    return true;
                } else return false;
            }
        } else return false;
    }

    void drawGrid() {
        for (int y = 0; y < _h; ++y) {
            for (int x = 0; x < _w; ++x) {
                if (grid.at(y * w + x)) cout << "|S";
                else cout << "|_";
            }
            cout << "|" << endl;
        }
        cout << endl;
    }

    void hitXY(unsigned x, unsigned y) {
        if ((x <= _w) && (y <= _h)) {
            if (grid[y * _w + x]) cout << "You sunk my battleship" << endl;
            else cout << "Nothing..." << endl;
        }
    }

private:
    QVector<Ship *> grid;
    unsigned _w, _h;
};

基本思想是创建一个任意大小的网格，并使其能够在任意坐标处“加载”任意长度的船只。您需要检查尺寸是否太大，如果瓷砖还没有被占用，那就差不多了，另一件事是方向 - 如果水平，则增量为 +1，如果垂直增量为 + 宽度。

这为使用这些方法快速填充随机数据提供了灵活性：

int main() {
    Grid g(20, 20);
    g.drawGrid();
    unsigned shipCount = 20;

    while (shipCount) {
        Ship * s = new Ship(qrand() % 8 + 2, qrand() %2);
        if (g.addShip(s, qrand() % 20, qrand() % 20)) --shipCount;
        else delete s;
    }
    cout << endl;
    g.drawGrid();

    for (int i = 0; i < 20; ++i) g.hitXY(qrand() % 20, qrand() % 20);
}

当然，您可以进一步扩展它，使被击中的船只下沉并从网格中消失，使船只四处移动并翻转它们的方向成为可能。您甚至可以使用对角线方向。通过改进基于 OOP 的解决方案，可以利用很多灵活性和潜力。

显然，您将在生产代码中设置一些限制，因为目前您可以创建 0x0 的网格和长度为 0 的船舶。无论如何，这只是一个简单的示例。我使用的是 Qt，因此使用的是 Qt 容器，但它与 std 容器相同。

于 2013-08-20T22:25:21.437 回答
1

我可以在您的代码中看到一个潜在的无限循环

int j = 0;
if(i == 1) j= (i+1);
else j= i;

for(int k = -j/2; k <= j/2; k++)
{
    int numberOfCorrectLocation = 0;
    while(numberOfCorrectLocation != i)
    {
        if(row+k> 0 && row+k<8)
        {
            if(Grid[(row)*8+(column+k)] == 1) break;
            numberOfCorrectLocation++;
        }
    }
    if(numberOfCorrectLocation !=i) break;
}

在这里，没有什么可以阻止 row 为 0，因为它之前被分配了 rand%8，并且 k 可以被分配一个负值（因为 j 可以是正数）。一旦发生这种情况，什么都不会结束 while 循环。

另外，我建议以更面向对象的方式重新解决这个问题（或者至少将 main() 中的代码分解为多个更短的函数）。就我个人而言，我发现代码有点难以理解。

于 2013-08-20T21:37:54.503 回答
-1

我试图用 Java 重写你的程序，它可以按要求工作。随意询问任何未明确编码的内容。我没有重新检查它，所以它可能有自己的错误。它可以进一步优化和清理，但由于这里已经过了午夜，我现在不想这样做:)

public static void main(String[] args) {

    Random generator = new Random();

    int Grid[][] = new int[8][8];

    for (int battleShips = 0; battleShips < 5; battleShips++) {
        boolean isHorizontal = generator.nextInt(2) == 0 ? true : false;

        boolean battleShipFilled = false;

        while (!battleShipFilled) {             
            // Select a random row and column for trial             
            int row = generator.nextInt(8);
            int column = generator.nextInt(8);

            while (Grid[row][column] == 1) {
                row = generator.nextInt(8);
                column = generator.nextInt(8);
            }

            int lengthOfBattleship = 0;
            if (battleShips == 0) // Smallest ship should be of length 2
                lengthOfBattleship = (battleShips + 2);
            else    // Other 4 ships has the length of 2, 3, 4 & 5
                lengthOfBattleship = battleShips + 1;

            int numberOfCorrectLocation = 0;

            for (int k = 0; k < lengthOfBattleship; k++) {
                if (isHorizontal && row + k > 0 && row + k < 8) {
                    if (Grid[row + k][column] == 1)
                        break;
                } else if (!isHorizontal && column + k > 0 && column + k < 8) {
                    if (Grid[row][column + k] == 1)
                        break;
                } else {
                    break;
                }

                numberOfCorrectLocation++;
            }

            if (numberOfCorrectLocation == lengthOfBattleship) {
                for (int k = 0; k < lengthOfBattleship; k++) {
                    if (isHorizontal)
                        Grid[row + k][column] = 1;
                    else
                        Grid[row][column + k] = 1;
                }
                battleShipFilled = true;
            }

        }
    }
}

一些重要的点。

  • 正如@Kindread 在另一个答案中所说，代码具有必须消除的无限循环条件。

  • 这个算法会使用太多的资源来寻找解决方案，应该进行优化。

  • 应该避免代码重复，因为它会导致更多的维护成本（这对于这种特定情况可能不是问题）和可能的错误。

希望这个答案有帮助...

于 2013-08-20T22:20:30.157 回答