saru95 saru95 - 2 months ago 26
C++ Question

Algorithm for finding a plus sign 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 its 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...
Comments