saru95 - 4 months ago 48

C++ Question

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:

- Find a location with and with
`#`

on all its 4 directions. Like`#`

in figure 1.`(2, 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).
- Keep visiting and adding neighbors pertaining to that particular direction.
- 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

`#`

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&¤t_x<n&¤t_y>=0&¤t_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`

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