Maximum Boarders

Problem

You are given a table with n rows and m columns. Each cell is colored with white or black. Considering the shapes created by black cells, what is the maximum border of these shapes?A shape is a set of connected cells. Two cells are connected if they share an edge. Note that no shape has a hole in it.


C++ Solution:


  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int maxn = 1e3 + 14;
  5. char c[maxn][maxn];
  6.  int main(){
  7.  ios::sync_with_stdio(0), cin.tie(0);
  8.  int t;
  9.  cin >> t;
  10.  while(t--){
  11.  int n, m;
  12.  cin >> n >> m;
  13.  for(int i = 1; i <= n; i++)
  14.  cin >> (c[i] + 1);
  15.  int ans = 0;
  16.  for(int i = 1; i <= n; i++)
  17.  for(int j = 1, ptr = 1; j <= m; j = ptr)
  18.  if(c[i][j] != '#' || c[i - 1][j] == '#')
  19.  ptr++;
  20.  else{
  21.  while(c[i][ptr] == '#' && c[i - 1][ptr] != '#')
  22.  ptr++;
  23.  ans = max(ans, ptr - j);
  24.  }
  25.  for(int i = 1; i <= n; i++)
  26.  for(int j = 1, ptr = 1; j <= m; j = ptr)
  27.  if(c[i][j] != '#' || c[i + 1][ptr] == '#')
  28.  ptr++;
  29.  else{
  30.  while(c[i][ptr] == '#' && c[i + 1][ptr] != '#')
  31.  ptr++;
  32.  ans = max(ans, ptr - j);
  33.  }
  34.  for(int i = 1; i <= m; i++)
  35.  for(int j = 1, ptr = 1; j <= n; j = ptr)
  36.  if(c[j][i] != '#' || c[j][i - 1] == '#')
  37.  ptr++;
  38.  else{
  39.  while(c[ptr][i] == '#' && c[ptr][i - 1] != '#')
  40.  ptr++;
  41.  ans = max(ans, ptr - j);
  42.  }
  43.  for(int i = 1; i <= m; i++)
  44.  for(int j = 1, ptr = 1; j <= n; j = ptr)
  45.  if(c[j][i] != '#' || c[j][i + 1] == '#')
  46.  ptr++;
  47.  else{
  48.  while(c[ptr][i] == '#' && c[ptr][i + 1] != '#')
  49.  ptr++;
  50.  ans = max(ans, ptr - j);
  51.  }
  52.  cout << ans << '\n';
  53.  }
  54. }
Note:
       We Are Providing Every Content in this Blog Inspired From Many People and Provide it Open To All People Who Are Willing Gain Some Stuff in Computer Science.

Comment Below for Doubts&Queries