在网格中查找加号的算法

Question

我遇到了在给定网格中找到最大 'PLUS' 的问题。例如，如果我有以下网格：

..#..
..#.#
#####
..#.#
..#..

其中最大的 'PLUS' 尺寸为 3 。同样，对于

..#
#.#
#.#

答案是 1，因为没有特定的 'PLUS' 存在（当然除了起源）。

我想到的算法是这样的：

找到一个 # 且所有 4 个方向都为 # 的位置。如图1中的(2, 2)
使用广度优先搜索策略将其所有邻居及其所在的方向（左、右、上、下）添加到队列中。
继续访问并添加属于该特定方向的邻居。
重复，直到遇到 . 或运行出界。

在做所有这些的同时，我们可以维护一个数组，该数组可以维护 # 在每个方向上发生的计数。

代码：

int x[4] = {-1,0,1,0} ;
int y[4] = {0,1,0,-1} ;
int n, dir[4], result ;
char adj[2001][2001] ;

int bfs(int sx, int sy) {
    queue < pair <int, pair <int, int> > > q ;
    q.push(make_pair(0, make_pair(sx+x[0], sy+y[0]))) ;
    q.push(make_pair(1, make_pair(sx+x[1], sy+y[1]))) ;
    q.push(make_pair(2, make_pair(sx+x[2], sy+y[2]))) ;
    q.push(make_pair(3, make_pair(sx+x[3], sy+y[3]))) ;
    while (!q.empty()) {
        pair <int, pair <int, int> > curr = q.front() ;
        q.pop() ;
        int current_direction =  curr.first ;
        int current_x = curr.second.first + x[current_direction] ;
        int current_y = curr.second.second + y[current_direction] ;
        if (current_x>=0&&current_x<n&&current_y>=0&&current_y<n) {
            if (adj[current_x][current_y] == '#') {
                ++dir[current_direction] ;
                q.push(make_pair(current_direction, make_pair(current_x, current_y))) ;
            }
            else
                break ;
        }
        else
            break ;
    }
    result = *min_element(dir, dir+4) ;
    return result ;
}

int main() {
    int t ; scanf("%d", &t) ;
    while (t--) {
        scanf("%d", &n) ;
        for (int i = 0; i < n; i++)
            cin >> adj[i] ;
        bool flag = true ;
        int max_plus = 0 ;
        for (int i = 1; i < n - 1; i++)
            for (int j = 1; j < n - 1; j++) {
                if (adj[i][j] == '#' && adj[i-1][j] == '#' \
                    && adj[i][j+1] == '#' && adj[i+1][j] == '#' \
                    && adj[i][j-1] == '#') {
                    // cout << i << " " << j << endl ;
                    flag = false ;
                    memset(dir, 2, sizeof(dir)) ;
                    max_plus = max(max_plus, bfs(i, j)) ;
                }
            }
        if(flag)
            cout << "1" << endl ;
        else
            cout << max_plus << endl ;
    }
    return 0 ;
}

此代码似乎为图 1 提供了奇怪的输出 (33686019)。我似乎找不到关于代码的运行错误。另外，如果我的算法有问题，我会喜欢一些建议。

Answer 1

我不太清楚你的代码有什么问题，你的算法是否正确。但我不认为你需要 BFS 来解决这个问题。创建4个矩阵，保持每个#:

上下左右连续的#个数

..#..
..#.#
#####
..#.#
..#..

向上

..0..
..1.0
00201
..3.2
..4..

向下

..4..
..3.2
00201
..1.0
..0..

对

..0..
..0.0
43210
..0.0
..0..

左

..0..
..0.0
01234
..0.0
..0..

现在通过为每个元素保留最少 4 个矩阵来创建一个矩阵

分钟

..0..
..0.0
00200
..0.0
..0..

答案是 min 矩阵的最大值。

假设你想计算有多少个连续的'#'s are behind each '#'。

for i from 0 to str.length
    if s[i]=='#':
        if s[i-1]=='#': // beware of i==0
            dp[i] = dp[i-1]+1
        else 
            dp[i] = 0

str ..##.###...##...
dp  ..01.012...01...

在网格中查找加号的算法

Algorithm for finding a plus sign in a grid

c++

algorithm

grid

breadth-first-search