UVA 776 Solution- Monkeys in a Regular Forest

UVA 776 Solution- Monkeys in a Regular Forest 

It is simply floodfill problem. Here change is taking input and print correctly.

Two consecutive input is separated by % sign. Finally EOF is the end of last input.

Main challenge is displaying output. Before displaying, should calculate the max width of a column. Then display the each element with max width.

I used width array to calculate the max width of every column.   

uva id: shoaib05
Accepted Time: 0.036

#include<cstdio>
#include<cstring>
#include<stack>
#include<iostream>
#include<iomanip>

using namespace std;
typedef pair<int,int> pr;
pr p;
int len,row,col;
char graph[1000][1000],input[2000];
int result[1000][1000],num;
int dx[] = {-1,-1,-1,0,0,1,1,1};
int dy[] = {-1,0,1,-1,1,-1,0,1};
bool flag=true,vis[1000][1000];

void floodfill(int xx,int yy)
{
result[xx][yy]=num;
stack<pr> st;
p=pair<int,int>(xx,yy);
st.push(p);
char ch=graph[xx][yy];
int i,j,x,y;
while(!st.empty())
{
p=st.top();
st.pop();
xx=p.first;
yy=p.second;
for(i=0;i<8;i++)
{
x=xx+dx[i];
y=yy+dy[i];
if(x>=0 && x<row && y>=0 && y<col && graph[x][y]==ch && vis[x][y]==false)
{
result[x][y]=num;
vis[x][y]=true;
p=pair<int,int>(x,y);
st.push(p);
}
}
}
}
int main() 
{
freopen("file.txt","r",stdin);
int i,j,x,width[1000];
while(flag)
{
flag=false; /* flag for checking end of input is done by % or EOF. */
row=0;
while(gets(input))
{
if(input[0]=='%')
{
flag=true; /* flag is true, this means end of current input by %. this also clarify it is not last input */
break;
}
len=strlen(input);
for(col=0,j=0;j<len;col++,j=j+2)
graph[row][col]=input[j];
row++;
}
num=1; /* current number of species */
memset(vis,false,sizeof(vis));
/* calculate the output table */
for(i=0;i<row;i++)
{
for(j=0;j<col;j++)
{
if(!vis[i][j])
{
floodfill(i,j);
num++;
}
}
}
for(i=0;i<col;i++)
{
width[i]=0;
/* Calculate the max element for every column and store in width[i] */
for(j=0;j<row;j++)
width[i]=width[i]>result[j][i]?width[i]:result[j][i];
x=1;
/* calculate number of digit in width[i] */
while(true)
{
width[i]=width[i]/10;
if(width[i]==0)
break;
else
x++;
}
width[i]=x;
}
col--;
for(i=0;i<row;i++)
{
for(j=0;j<col;j++)
{
cout<<setw(width[j])<<result[i][j]<<" ";
}
cout<<setw(width[col])<<result[i][j]<<endl;
}
cout<<"%"<<endl;
}
return 0;
}

Input:

A A D E C C D
F F A D a b D
P A E A A D P
%
a b c d e f g h
i j k l m n o p
q r s t u v w x

Output:

1 1  2 3 4 4  5
6 6  1 2 7 8  5
9 1 10 1 1 5 11
%
 1  2  3  4  5  6  7  8
 9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
%