saru95 saru95 - 3 months ago 13
C++ Question

Algorithm for finding a figure in a grid

I have this problem of finding the largest 'PLUS' in a given grid .
For example , If I have the following grid .

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


The largest 'PLUS' in it would be of size 3 . Similarly, for

..#
#.#
#.#


the answer would be 1 as no particular 'PLUS' exists (except the origin of course) .

The algorithm I have in mind goes like this :


  1. Find a location with
    #
    and with
    #
    on all its 4 directions . Like
    (2, 2)
    in figure 1 .

  2. Use Breadth First Search strategy to add all the neighbors in the queue along with the direction they lie in (left, right, up, down) .

  3. Keep visiting and adding neighbors pertaining to that particular direction .

  4. Repeat until you encounter a '
    .
    ' or run out of bounds .



While doing all this, we can maintain an array which can maintain the count of
#
occurring in each direction .

Code :

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


This code seems to give a weird output (
33686019
) for figure 1 .
I can't seem to find the error I'm running into with respect to the code . Also, if there is something wrong with the algorithm I have, I'd love some advice .

Answer

I don't exactly know what is wrong with your code and whether your algorithm is correct or not. But I don't think you need BFS to solve this problem. Create 4 matrices that keeps the number of consecutive #s up, down, left and right of each #:

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

up

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

down

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

right

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

left

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

now create a matrix by keeping the minimum of 4 matrices for each element

min

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

The answer is maximum of the min matrix.

suppose you want to count how many consecutive '#'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...