#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define int long long
using namespace std;
const int mod=1e9+7,mxn=1e5+5,inf=1e18,minf=-1e18,lg=30,valbound=1e9;
//#undef int
int k,m,q,p,h,w,n;
void setIO(string name){
ios_base::sync_with_stdio(0); cin.tie(0);
freopen((name+".in").c_str(),"r",stdin);
freopen((name+".out").c_str(),"w",stdout);
}
int grid[mxn+10][55],vis[mxn+10][55];
int ans=0,x=inf,y=minf;
int u[8]={1,-1,0,0,1,1,-1,-1},r[8]={0,0,1,-1,1,-1,1,-1};
void get(int cx,int cy){
x=min(x,cx);
y=max(y,cy);
vis[cx][cy]=1;
for(int i=0;i<8;i++){
int nx=cx+u[i],ny=cy+r[i];
if(nx<=0||nx>n||ny<=0||ny>m){
x=1,y=n;//border case ->dont count
continue;
}
if(vis[nx][ny])continue;
if(grid[nx][ny])continue;
get(nx,ny);
}
}
int32_t main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
string a;cin>>a;
for(int j=0;j<m;j++)grid[i][j+1]=a[j]-'0';
}
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(grid[i][j])ans+=(i*(n-i+1));
for(int i=2;i<=n;i++)for(int j=1;j<=m;j++)if(grid[i][j]&&grid[i-1][j])ans-=((i-1)*(n-i+1));
for(int i=1;i<=n;i++)for(int j=2;j<=m;j++)if(grid[i][j]&&grid[i][j-1])ans-=(i*(n-i+1));
for(int i=2;i<=n;i++)for(int j=2;j<=m;j++)if(grid[i][j]&&grid[i][j-1]&&grid[i-1][j]&&grid[i-1][j-1])ans+=((i-1)*(n-i+1));
//case 4
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(!vis[i][j]&&grid[i][j]==0){
x=inf,y=minf;
get(i,j);
ans+=((x-1)*(n-y));
}
cout<<ans;
}
/*
what if we look at each cell as a seperated node
then we can see that the vertical edges connect 2 node together
so we will know that l,r that cover i will have comp -=1
how about the horizontal edges?
we can make all the node that shared vertical edge into one comp
we can make a graph with only horizontal edges
we can see that for a cycle let x,y = min and max row in the cycle
we can see that one of the edge is useless as it connect 2 of the same comp
when there are multiple cycle in a cycle we will take min,max from the small cycle
each cycle will make a hole? except for the size 4
we can oversubtract then add back by counting holes?
4 4
1101
1111
1010
1011
5 7
0100010
0111110
0101001
1111011
0100100
4 12
011111010111
110000101001
110111101111
111101111111
*/
Compilation message
raspad.cpp:32:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
32 | #pragma GCC optimize ("03,unroll-lopps")
| ^
raspad.cpp:38:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
38 | void setIO(string name){
| ^
raspad.cpp:46:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
46 | void get(int cx,int cy){
| ^
raspad.cpp:61:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
61 | int32_t main(){
| ^
raspad.cpp: In function 'void setIO(std::string)':
raspad.cpp:40:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
40 | freopen((name+".in").c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
raspad.cpp:41:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
41 | freopen((name+".out").c_str(),"w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
27 ms |
22616 KB |
Output is correct |
| 2 |
Incorrect |
159 ms |
95448 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
