#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e9;
const int N = 1e5+1;
void solve() {
int n,m;
cin >> n >> m;
vector<string> grid(n);
for (auto& row : grid) cin >> row;
int r[n][m]{},d[n][m]{};
for (int i = 0;i<n;i++) {
for (int j = m-1;j>=0;j--) {
if (grid[i][j] == '0') {
r[i][j] = inf;
continue;
}
if (j!=m-1) r[i][j] = (r[i][j+1]<inf)*r[i][j+1]+1;
else r[i][j] = 1;
}
}
for (int j = 0;j<m;j++) {
for (int i = n-1;i>=0;i--) {
if (grid[i][j] == '0') {
d[i][j] = inf;
continue;
}
if (i!=n-1) d[i][j] = (d[i+1][j]<inf)*d[i+1][j]+1;
else d[i][j] = 1;
}
}
int mn1 = n,mn2 = m;
for (int i = 0;i<n;i++) {
for (int j = 0;j<m;j++) {
if (!j || grid[i][j-1] == '0') mn2 = min(mn2,r[i][j]);
if (!i || grid[i-1][j] == '0') mn1 = min(mn1,d[i][j]);
}
}
cout << mn1 sp mn2 << endl;
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef Dodi
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int t = 1;
//cin >> t;
while (t --> 0) solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |