이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> II;
const int N = 1e5 + 5, logN = 20;
const int MOD = 1e9 + 7;
const ll INF = 1e9;
int n, m, vis[N][55], minx, maxx, comp[N][55], nComp;
char a[N][55];
vector<II> vt;
inline bool inside(int x, int y){
return x >= 1 && x <= n && y >= 1 && y <= m;
}
void dfs(int x, int y){
vis[x][y] = true;
vt.push_back(II(x, y));
comp[x][y] = nComp;
minx = min(minx, x);
maxx = max(maxx, x);
for(int nx = x - 1; nx <= x + 1; nx ++){
for(int ny = y - 1; ny <= y + 1; ny ++){
if(inside(nx, ny) && !vis[nx][ny] && a[nx][ny] == '0') dfs(nx, ny);
}
}
}
int main(){
//freopen("datpat.inp", "r", stdin);
//freopen("datpat.out", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++) cin >> a[i][j];
}
ll ans = 0;
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++){
if(a[i][j] == '1'){
ans += i * 1ll * (n - i + 1);
if(a[i - 1][j] == '1') ans -= (i - 1) * 1ll * (n - i + 1);
if(a[i][j - 1] == '1') ans -= i * 1ll * (n - i + 1);
if(a[i - 1][j] == a[i][j - 1] && a[i - 1][j] == '1' && a[i - 1][j - 1] == '1') ans += (i - 1) * 1ll * (n - i + 1);
}
}
}
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++){
if(!vis[i][j] && a[i][j] == '0'){
minx = INF;
maxx = -INF;
nComp ++;
vt.clear();
dfs(i, j);
bool check = true;
for(auto xy : vt){
int x = xy.first, y = xy.second;
for(int nx = x - 1; nx <= x + 1; nx ++){
for(int ny = y - 1; ny <= y + 1; ny ++) check &= (comp[nx][ny] == nComp || a[nx][ny] == '1');
}
}
if(check) ans += (minx - 1) * 1ll * (n - maxx);
}
}
}
cout << ans << endl;
return 0;
}
/*
5 7
0100010
0111110
0101001
1111011
0100100
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |