Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<algorithm>
- #include<vector>
- using namespace std;
- using ll = long long;
- template<typename T> using V = vector<T>;
- template<typename T1, typename T2 = T1> using P = pair<T1, T2>;
- void _debug() {cerr << endl;}
- template<typename T, typename... Args>
- void _debug(const T& a, Args... b) {cerr << a << ' ', _debug(b...);}
- #define debug(...) cerr<<'('<<#__VA_ARGS__<<"): ", _debug(__VA_ARGS__)
- template<typename T>
- ostream& operator<<(ostream& os, const V<T>& v) {
- for (const auto& i : v)
- os << i << ' ';
- return os;
- }
- inline void solve() {
- int n, m; cin >> n >> m;
- V<string> v(n);
- for (auto& i : v) cin >> i;
- V<V<int>> uu(n, V<int>(m, 0)), ur(uu), ll(uu), lu(uu), dd(uu), dl(uu), rr(uu), rd(uu);
- for (int i = 0; i + 1 < m; i++)
- if (v[0][i + 1] == '1')
- ur[0][i] = 1;
- for (int i = 1; i < n; i++)
- for (int j = m - 1; j >= 0; j--) {
- if (v[i - 1][j] == '1')
- uu[i][j] = ur[i - 1][j] + 1;
- if (j + 1 < m && v[i][j + 1] == '1')
- ur[i][j] = uu[i][j + 1] + 1;
- }
- for (int i = 1; i < n; i++)
- if (v[i - 1][0] == '1')
- lu[i][0] = 1;
- for (int j = 1; j < m; j++)
- for (int i = 0; i < n; i++) {
- if (v[i][j - 1] == '1')
- ll[i][j] = lu[i][j - 1] + 1;
- if (i - 1 >= 0 && v[i - 1][j] == '1')
- lu[i][j] = ll[i - 1][j] + 1;
- }
- for (int i = 1; i < m; i++)
- if (v[0][i - 1] == '1')
- dl[n - 1][i] = 1;
- for (int i = n - 2; i >= 0; i--)
- for (int j = 0; j < m; j++) {
- if (v[i + 1][j] == '1')
- dd[i][j] = dl[i + 1][j] + 1;
- if (j - 1 >= 0 && v[i][j - 1] == '1')
- dl[i][j] = dd[i][j - 1] + 1;
- }
- for (int i = 0; i + 1 < n; i++)
- if (v[i + 1][m - 1] == '1')
- rd[i][m - 1] = 1;
- for (int j = m - 2; j >= 0; j--)
- for (int i = n - 1; i >= 0; i--) {
- if (v[i][j + 1] == '1')
- rr[i][j] = rd[i][j + 1] + 1;
- if (i + 1 < n && v[i + 1][j] == '1')
- rd[i][j] = rr[i + 1][j] + 1;
- }
- debug(uu); debug(ll); debug(rr); debug(dd);
- debug(ur); debug(lu); debug(dl); debug(rd);
- int ans = 0;
- for (int i = 0; i < n; i++)
- for (int j = 0; j < m; j++)
- ans = max(ans, uu[i][j] + ll[i][j] + rr[i][j] + dd[i][j]);
- cout << ans << endl;
- }
- signed main() {
- int T = 1;
- cin >> T;
- while (T--)
- solve();
- return 0;
- }
Advertisement
RAW Paste Data
Copied
Advertisement