Advertisement
konchin_shih

pI

Jul 1st, 2022
692
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.19 KB | None
  1. #include<iostream>
  2. #include<algorithm>
  3. #include<vector>
  4. using namespace std;
  5. using ll = long long;
  6. template<typename T> using V = vector<T>;
  7. template<typename T1, typename T2 = T1> using P = pair<T1, T2>;
  8. void _debug() {cerr << endl;}
  9. template<typename T, typename... Args>
  10. void _debug(const T& a, Args... b) {cerr << a << ' ', _debug(b...);}
  11. #define debug(...) cerr<<'('<<#__VA_ARGS__<<"): ", _debug(__VA_ARGS__)
  12. template<typename T>
  13. ostream& operator<<(ostream& os, const V<T>& v) {
  14.     for (const auto& i : v)
  15.         os << i << ' ';
  16.     return os;
  17. }
  18. inline void solve() {
  19.     int n, m; cin >> n >> m;
  20.     V<string> v(n);
  21.     for (auto& i : v) cin >> i;
  22.     V<V<int>> uu(n, V<int>(m, 0)), ur(uu), ll(uu), lu(uu), dd(uu), dl(uu), rr(uu), rd(uu);
  23.     for (int i = 0; i + 1 < m; i++)
  24.         if (v[0][i + 1] == '1')
  25.             ur[0][i] = 1;
  26.     for (int i = 1; i < n; i++)
  27.         for (int j = m - 1; j >= 0; j--) {
  28.             if (v[i - 1][j] == '1')
  29.                 uu[i][j] = ur[i - 1][j] + 1;
  30.             if (j + 1 < m && v[i][j + 1] == '1')
  31.                 ur[i][j] = uu[i][j + 1] + 1;
  32.         }
  33.     for (int i = 1; i < n; i++)
  34.         if (v[i - 1][0] == '1')
  35.             lu[i][0] = 1;
  36.     for (int j = 1; j < m; j++)
  37.         for (int i = 0; i < n; i++) {
  38.             if (v[i][j - 1] == '1')
  39.                 ll[i][j] = lu[i][j - 1] + 1;
  40.             if (i - 1 >= 0 && v[i - 1][j] == '1')
  41.                 lu[i][j] = ll[i - 1][j] + 1;
  42.         }
  43.     for (int i = 1; i < m; i++)
  44.         if (v[0][i - 1] == '1')
  45.             dl[n - 1][i] = 1;
  46.     for (int i = n - 2; i >= 0; i--)
  47.         for (int j = 0; j < m; j++) {
  48.             if (v[i + 1][j] == '1')
  49.                 dd[i][j] = dl[i + 1][j] + 1;
  50.             if (j - 1 >= 0 && v[i][j - 1] == '1')
  51.                 dl[i][j] = dd[i][j - 1] + 1;
  52.         }
  53.     for (int i = 0; i + 1 < n; i++)
  54.         if (v[i + 1][m - 1] == '1')
  55.             rd[i][m - 1] = 1;
  56.     for (int j = m - 2; j >= 0; j--)
  57.         for (int i = n - 1; i >= 0; i--) {
  58.             if (v[i][j + 1] == '1')
  59.                 rr[i][j] = rd[i][j + 1] + 1;
  60.             if (i + 1 < n && v[i + 1][j] == '1')
  61.                 rd[i][j] = rr[i + 1][j] + 1;
  62.         }
  63.     debug(uu); debug(ll); debug(rr); debug(dd);
  64.     debug(ur); debug(lu); debug(dl); debug(rd);
  65.     int ans = 0;
  66.     for (int i = 0; i < n; i++)
  67.         for (int j = 0; j < m; j++)
  68.             ans = max(ans, uu[i][j] + ll[i][j] + rr[i][j] + dd[i][j]);
  69.     cout << ans << endl;
  70. }
  71. signed main() {
  72.     int T = 1;
  73.     cin >> T;
  74.     while (T--)
  75.         solve();
  76.     return 0;
  77. }
Advertisement
RAW Paste Data Copied
Advertisement