352 – The Seasonal War

Problem Link

#Ideone (with testcase)

#Solution

#include<bits/stdc++.h>
#define fr(i,n) for(int i=1;i<=n;i++)
#define xx first
#define yy second
using namespace std;
int n;

int dx[]={1,-1,0,0,-1,-1,1,1};
int dy[]={0,0,-1,1,-1,1,-1,1};
#define pii pair<int,int>
bool vis[100][100];
char g[100][100];

void bfs(int sx,int sy)
{
vis[sx][sy]=1;
queueq;
q.push(pii(sx,sy));
while(!q.empty())
{
pii u=q.front();
q.pop();
pii t;
for(int i=0;i<8;i++){ t.xx=u.xx+dx[i]; t.yy=u.yy+dy[i]; if(t.xx>=1 &&t.xx<=n &&t.yy>=1 &&t.yy<=n &&g[t.xx][t.yy]==’1′ &&!vis[t.xx][t.yy]) { vis[t.xx][t.yy]=1; q.push(pii(t.xx,t.yy)); } } } } int main() { int cs=1; while(cin>>n && n){

memset(vis,0,sizeof vis);

fr(i,n) fr(j,n)
cin>>g[i][j];
int co=0;
fr(i,n) fr(j,n)
if(g[i][j]==’1′ &&vis[i][j]==0)
{
bfs(i,j);
co++;
}
printf(“Image number %d contains %d war eagles.\n”,cs++,co);

}
return 0;
}

Advertisements

About waprogramming

I am in CSE,from CUET
This entry was posted in Uncategorized, uva and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s