After reaching Cluj-Napoca, Comisia got bored again. While trying to find something interesting to do, she realised that Cluj-Napoca is a city with N parallel streets, each one consisting of M parallel avenues. She also knows that population defines a block as the intersection of a street with an avenue. She also discovered that some of the blocks are occupied with constructions (we call them 0 blocks) and some are unoccupied (we call them 1 blocks). One may freely walk through a 1 block without any restriction, but walking through a 0 block is strictly forbidden by the local private property laws.
Comisia (as you already know) very easily gets bored, so she will never visit the same block twice (except for the starting block). She defines a walk as a succession of 1 blocks, where every two consecutive blocks share a common edge. Also, a walk cannot end in a different place than where it started (this makes the walk more interesting) and its length must be at least 4 (because short walks are boring).
With these in mind, Comisia decided to find out how many 1 blocks can be the beginning of a valid walk. Because Cluj-Napoca is a big city, she asks you to write her a program which, for a given map of the city, computes the answer to her problem.
Input
The first line of the input will containN and M. Each of the following N lines contains the description of a street: M characters (0 or 1). Output
The first and only line of the output should contain the answer to Comisia's problem.Constraints
1 ≤ N, M ≤ 500Sample
| Input | Output | Explanation |
|---|---|---|
| 3 4 1111 1101 1101 | 6 | There are 6 places from where Comisia may start a valid walk. |
O(n2*m2)
Putem considera matricea ca fiind un graf neorientat, cu noduri in patratele cu 1. Acum, daca construim cate un arbore dfs din fiecare nod al grafului, cel putin un ciclu ce contine nodul din care am pornit parcurgerea dfs va fi format din muchii de arbore si o singura muchie inversa (in cazul in care exista un astfel de ciclu). Se demonstreaza usor ca o muchie de intoarcere cu un capat in nodul de plecare este necesara si suficienta pentru un ciclu din nodul de placere. Aceasta solutie este ineficienta, neincadrandu-se in timp. O(n*m)
Solutia buna se bazeaza pe solutia de mai sus. Problema este strans legata de determinarea punctelor de articulatie ale grafului. Pentru aceasta vom construi arborele dfs al grafului. Vom retine pentru fiecare nod h[i] - inaltimea nodului i din graf si o dinamica low[i] = cea mai mica inaltime la care se poate ajunge plecand din nodul i, mergand pe un lant in jos si apoi pe o muchie de intoarcere. Cu acestea cunoscute (relatia de recurenta este aceasi ca cea de la determinarea punctelor de articulatie), un nod i face parte din cel putin un ciclu daca si numai daca low[i]<=h[i] . Complexitatea toatala este astfel O(n*m), construind cate un astfel de arbore pentru fiecare componenta conexa a grafului. 1 void dfs(int i,int j,int a,int b, int h) { 2 viz[i][j]=1; 3 depth[i][j]=low[i][j]=h; 4 int ok=0; 5 for(int d=0; d<4; ++d) { 6 int ii=i+dx[d],jj=j+dy[d]; 7 if(!isIn(ii,jj) || mt[ii][jj]=='0') continue; 8 if(ii==a && jj==b) continue; 9 if(!viz[ii][jj]) { 10 dfs(ii,jj,i,j,h+1); 11 if(low[ii][jj]<=depth[i][j]) ok=1; 12 low[i][j]=min(low[i][j],low[ii][jj]); 13 }else { 14 low[i][j]=min(low[i][j],depth[ii][jj]); 15 if(depth[ii][jj]<=depth[i][j]) ok=1; 16 } 17 } 18 rez+=ok; 19 } 20
