# MOLECULE GRID Solutions BVPCSI05

Page Contents

### MOLECULE GRID Solutions BVPCSI05

Given a 2−d matrix guide of ′1′s(Air−molecule) and ‘0′s(vacuum), check the quantity of Air Moles. An Air mole is encircled by vacuum and is framed by interfacing adjoining air atoms evenly or vertically. You may accept every one of the four edges of the framework are completely encircled by vacuum.

Info

N−rows,m−columns

Yield

Print the quantity of Air moles.

Limitations

(1<=n,m<=1e5)

Test Input

4 5

11110

11010

11000

00000

Test Output

Test Input

4 5

11000

11000

00100

00011

Test Output

3

``Solution``
``CODE C++14 :``
` `
`#include <bits/stdc++.h>`
`using namespace std;`
`#define int long long`
`int row[] = { -1, 0, 0, 1};`
`int col[] = { 0, -1, 1, 0};`
`int32_t main() `
`{`
`	ios_base::sync_with_stdio(false);`
`	cin.tie(NULL);`
` `
`	int n,m;`
`	cin>>n>>m;`
`	int i,j,k;`
`	string s;`
`	int mat[n][m];`
`	for(i=0;i<n;++i)`
`	{`
`		cin>>s;`
`		for(j=0;j<m;++j)`
`		{`
`			mat[i][j]=s[j]-'0';`
`		}`
`	}`
`	bool processed[n][m];`
`	memset(processed, 0, sizeof(processed));`
`	int ctr = 0;`
`	for (i = 0; i < n; i++)`
`	{`
`		for (j = 0; j < m; j++)`
`		{`
` `
`			if (mat[i][j] && processed[i][j] == 0)`
`			{`
`				queue<pair<int, int>> q;`
`				q.push(make_pair(i, j));`
`				processed[i][j] = true;`
`				while (!q.empty())`
`				{`
`					int x = q.front().first;`
`					int y = q.front().second;`
`					q.pop();`
` `
` `
`					for (k = 0; k < 4; k++)`
`					{`
`						if ((x + row[k] >= 0) && (x + row[k] < n) && (y + col[k] >= 0) && (y + col[k] < m) &&`
`		(mat[x + row[k]][y + col[k]] && !processed[x + row[k]][y + col[k]]))`
`						{`
`							processed[x + row[k]][y + col[k]] = 1;`
`							q.push(make_pair(x + row[k], y + col[k]));`
`						}`
`					}`
`				}			`
`				ctr++;`
`			}`
`		}`
`	}`
`	cout<<ctr;`
`}`
` `