Алгоритм поиска знака плюса в сетке

Question

У меня есть эта проблема нахождения наибольшего «ПЛЮСА» в заданной сетке. Например, если у меня есть следующие сетки:

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

Самый большой «плюс» в нем будет размером 3. Аналогичным образом, для

..# 
#.# 
#.# 

Ответ будет 1, поскольку нет особого «ПЛЮСА» (за исключением происхождения, конечно).

алгоритм я имею в виду, выглядит следующим образом:

1. Найти место с # и # на всех своих 4-х направлениях. Например, (2, 2) на рисунке 1.
2. Используйте стратегию поиска по пятам, чтобы добавить всех своих соседей в очередь вместе с направлением, в котором они лежат (слева, справа, вверх, вниз).
3. Продолжайте посещать и добавлять соседей по этому направлению.
4. Повторяйте, пока не столкнетесь с . или не пройдете границу.

Выполняя все это, мы можем поддерживать массив, который может поддерживать счет #, происходящий в каждом направлении.

Код:

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 ; 
} 

Этот код, кажется, дает странный вывод (33686019) для рисунка 1. я не могу показаться, чтобы найти ошибку, я бегу в отношении кода. Кроме того, если что-то не так с алгоритмом, который у меня есть, мне бы понравился совет.

Answer 1

Я точно не знаю, что не так с вашим кодом и правильно ли ваш алгоритм. Но я не думаю, что вам нужна BFS для решения этой проблемы. Создание 4-матрицы, которые хранит число последовательных # S вверх, вниз, влево и вправо каждого #:

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

до

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

вниз

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

право

..0.. 
..0.0 

..0.0 
..0.. 

покинул

..0.. 
..0.0 

..0.0 
..0.. 

Теперь создать матрицу, сохраняя минимум 4 матриц для каждого элемента

мин

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

Ответ максимум min матрицы.

Предположим, вы хотите подсчитать, сколько последовательных «#» стоит за каждым «#».

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...