二维数组搜索算法优化

Question

我得到了一个长度和宽度可变的 "Sand box"。我得到的指示是找到一个 "shovel" 的静态大小，它可以水平或垂直定向。我实现了以下算法，以便在网格中搜索最少的次数来找到 one 有效位置（对应于 "part of the object" 的位置）：

found = false;
nShift = 0;
shovelSize = 4;
for(int i = 0; i < SandBoxRows; i++) {
    for(int j = 0; j < SandBoxColumns; j+=shovelSize) {
        found = probeSandBoxTwo(('A' + i), (j + 1 + nShift));
    }

    if(nShift >= shovelSize - 1 || nShift > SandBoxColumns) {
        nShift = 0;
    } else {
        nShift++;
    }
}

在这种情况下，"Sand box" 将通过下面描述的函数进行测试。

我用 "Sand box" 完全重现了这个场景，它的大小是固定的（尽管很容易操作），它的铲子仍然随机放置并在以下代码中定向：

#include <cstdlib>
#include <ctime>
#include <iostream>
using namespace std;

const int ROW = 12;
const int COL = 16;
char sandbox[ROW][COL];

bool probeSandBoxTwo(char c, int i);
void displayResults(int sCount, bool found, int x, int y);
void displaySandbox();
void displaySearchPattern();
void fillSandbox();
void placeShovel();

int main() {
    fillSandbox();
    placeShovel();
    displaySandbox();

    //define your variables here
    bool found;
    int nShift,
        sCount,
        shovelSize,
        x,
        y;


    found = false;
    nShift = 0;
    shovelSize = 4;
    sCount = 0;
    for(int i = 0; i < ROW && !found; i++) {
        for(int j = 0; j < COL && !found; j+=shovelSize) {
            found = probeSandBoxTwo(('A' + i), (j + 1 + nShift));
            x = i;
            y = j + nShift;
            sCount++;
            cout << "Search conducted at (" << i << ", " << (j + nShift) << ")" << endl;
        }

        if(nShift >= shovelSize - 1 || nShift > ROW) {
            nShift = 0;
        } else {
            nShift++;
        }
    }
    displayResults(sCount, found, x, y);
    displaySearchPattern();
}

bool probeSandBoxTwo(char c, int i) {
    if(sandbox[c-'A'][i-1] == 'X') {
        return true;
    } else {
        return false;
    }
}

void displayResults(int sCount, bool found, int x, int y) {
    cout << endl;
    cout << "Total searches: " << sCount << endl;
    cout << endl;
    if(found) {
        cout << "Shovel found at coordinates: (" << x << ", " << y << ")" << endl;
    }
}

void displaySandbox() {
    cout << "  ";
    for(int i = 0; i < COL; i++) {
        cout << (i % 10); //show index numbers [col]
    }
    cout << endl;
    for(int i = 0; i < ROW; i++) {
        cout << (i % 10) << " "; //show index numbers [row]
        for(int j = 0; j < COL; j++) {
            cout << sandbox[i][j];
        }
        cout << endl;
    }
    cout << endl;
}

void displaySearchPattern() {
    int nShift = 0;
    int shovelSize = 4;

    cout << endl << "  ";
    for(int i = 0; i < COL; i++) {
        cout << (i % 10); //show index numbers [col]
    }
    cout << endl;
    for(int i = 0; i < ROW; i++) {
        cout << (i % 10) << " "; //show index numbers [row]
        for(int j = 0; j < COL; j++) {
            if(!((j + nShift) % shovelSize)) {
                cout << 'o';
            } else {
                cout << '.';
            }
        }

        if(nShift >= shovelSize - 1 || nShift > COL) {
            nShift = 0;
        } else {
            nShift++;
        }
        cout << endl;
    }
}

void fillSandbox() {
    for(int i = 0; i < ROW; i++) {
        for(int j = 0; j < COL; j++) {
            sandbox[i][j] = '.';
        }
    }
}

void placeShovel() {
    srand(time(NULL));
    int shovelRow,
        shovelCol,
        shovelSize = 4;
    if(rand() % 2) {
        //horizontal
        shovelRow = rand() % ROW + 1;
        shovelCol = rand() % (COL - (shovelSize - 1)) + 1;
        for(int i = shovelCol - 1; i < shovelSize + (shovelCol - 1); i++) {
            sandbox[shovelRow - 1][i] = 'X';
        }
    } else {
        //vertical
        shovelRow = rand() % (ROW - (shovelSize - 1)) + 1;
        shovelCol = rand() % COL + 1;
        for(int i = shovelRow - 1; i < shovelSize + (shovelRow - 1); i++) {
            sandbox[i][shovelCol - 1] = 'X';
        }
    }
}

在此代码中，我还以图形方式显示了我的算法搜索的模式（当运行时）。

对于这种情况，这真的是最佳搜索模式吗？我的实现是否正确？如果是，为什么我会返回不正确的结果？

给定的测试驱动程序报告了以下结果：

source code for this result (and its test driver).

Answer 1

    found = false;
    nShift = 0;
    shovelSize = 4;
    for(int i = 0; i < SandBoxRows; i++) {
        for(int j = 0; (j + nShift) < SandBoxColumns; j+=shovelSize) {
            found = probeSandBoxTwo(('A' + i), (j + 1 + nShift));
        }

        if(nShift >= shovelSize - 1 || nShift > SandBoxColumns) {
            nShift = 0;
        } else {
            nShift++;
        }
    }

这更正了 for 循环头的条件部分中的一个错误，该部分没有考虑索引移位变量 nShift。

二维数组搜索算法优化

Two-Dimensional Array Searching Algorithm Optimisation

c++

arrays

algorithm

optimization

search