469 - Wetlands of Florida

[raysa]

Hello,
I found my solution for "Wetlands of Florida" WA in 0.402 sec.
I've matched my output to A.Kuegel's and it seems fine.
I'm afraid it's the multiple input problem <though I DID consider the m_input rule>.
So please tell me where to pay attention the most when handling the m_input in this prob.
I'll patch my code <or via private message> if it REALLY neccessary...

Thank you!
Raysa

[Jalal]

Yes ita a multiple input problem
u shoul see the bule right mark before the problem
indicates the multiple input problem

[raysa]

Ha-ha..!
Finally I found my mistake:
My floodfill function gives count=0 when there's only one 'W' in the area,
i.e. water on the starting point. It should be count=1. AC (P.E.) now...
Anyway, thank's for any attention!

Best regards,
Raysa

[titid_gede]

i still got wrong answer, dunno where the mistake was. anyway i am still confuse in understanding the problem. i wasn't sure by the statement "Given the row and column number of a grid cell that contains water, what is the area of the lake containing that cell". how if the cell contains 'L'? do i need to flood fill it, or just return 0 (outputing 0)?

[raysa]

I think you can just give it a 0, since the starting-point itself is not even a single "Water"...

G' Luck!
Raysa

[titid_gede]

i still got wrong answer,
i dont think that if the starting point not 'W' just give 0. since OJ give WA on 1.174 sec if i flood fill with starting point not 'W', and give WA on 0.178 if i flood fill only if starting point 'W'.
here is my code :

[c]
/*@JUDGE_ID: XXXXX 469 C*/
#include <stdio.h>
#include <ctype.h>
#include <string.h>

#define MAX 100

char data[MAX][MAX];

int flood_fill (char tempdata[MAX][MAX], char x, int a, int b, int i, int j, int *jum) {

if (tempdata[a] == x) {
*jum = *jum + 1;
tempdata[a] = 'C';
if (a != 0) {
flood_fill (tempdata, x, a-1, b, i, j, jum);
if (b != 0) flood_fill (tempdata, x, a-1, b-1, i, j, jum);
if (b != j-1) flood_fill (tempdata, x, a-1, b+1, i, j, jum);
}
if (b != 0)
flood_fill (tempdata, x, a, b-1, i, j, jum);
if (b != j-1)
flood_fill (tempdata, x, a, b+1, i, j, jum);
if (a != i-1) {
flood_fill (tempdata, x, a+1, b, i, j, jum);
if (b != 0) flood_fill (tempdata, x, a+1, b-1, i, j, jum);
if (b != j-1) flood_fill (tempdata, x, a+ 1, b+1, i, j, jum);
}
}
return 0;
}

int main () {
int cases, ct, i, j, a, b, jum;
char ch, tempdata[MAX][MAX];

scanf ("%d\n", &cases);

for (ct = 0; ct < cases; ct++) {
i = 0; j = 0;
ch = getchar();
while (!isalpha (ch)) ch = getchar();
while (1) {
if (isdigit (ch)) break;
if (isalpha (ch)) {
data[j] = ch;
j++;
} else if (ch == '\n') {
j = 0;
i++;
}
ch = getchar();
}
a = 0; b = 0;
while (1) {
if (ch == '\n') {
if ((a == 0) && (b == 0)) break;
memcpy (tempdata, data, sizeof(char)*MAX*MAX);
jum = 0;
flood_fill (tempdata, data[a-1][b-1], a-1, b-1, i, j, &jum);
printf ("%d\n", jum);
a = 0; b = 0;
} else if (isdigit (ch)) {
if (a == 0)
a += (a*10) + (ch-'0');
else
b += (b*10) + (ch-'0');
}
ch = getchar();
}

if (cases-1 != ct) printf ("\n");
}
return 0;
}

[/c]

[raysa]

Please note that in this problem, your task is:
1. to count how many 'W' connected to the starting point, IF THE STARTING POINT IS A 'W' --according to the Input part:

The pairs of integers on the last k lines, each represent the row and column numbers of some grid cell that contains water.

2. give a zero in any case but #1.
<At least those are what I've done ^_^ !>

However, consider this:
Input:

Code: Select all

1
LLLWL
LLWLL
1 1
1 4
2 2
2 6
2 7
3 1

Your code gives:
Output:

Code: Select all

8
2
8
9990
9990
<<Crash!>>

When mine is:
Output:

Code: Select all

0
2
0
0
0
0

P.S. About your username... Sorry, but please change it to one that more proper.

Good luck,
Raysa

[anak_papua]

i've fixed that problem and gave the same result as yours, but still WA. i dont know the mistake
perhaps there are special cases or somethin that might trap me?

[c]/*@JUDGE_ID: XXXXX 469 C*/
#include <stdio.h>
#include <ctype.h>
#include <string.h>

#define MAX 100

char data[MAX][MAX], tempdata[MAX][MAX];

int flood_fill (int a, int b, int i, int j, int *jum) {

if (tempdata[a] == 'W') {
*jum = *jum + 1;
tempdata[a] = 'C';
if (a != 0) {
flood_fill (a-1, b, i, j, jum);
if (b != 0) flood_fill (a-1, b-1, i, j, jum);
if (b != j-1) flood_fill (a-1, b+1, i, j, jum);
}
if (b != 0)
flood_fill (a, b-1, i, j, jum);
if (b != j-1)
flood_fill (a, b+1, i, j, jum);
if (a != i-1) {
flood_fill (a+1, b, i, j, jum);
if (b != 0) flood_fill (a+1, b-1, i, j, jum);
if (b != j-1) flood_fill (a+ 1, b+1, i, j, jum);
}
}
return 0;
}

int main () {
int cases, ct, i, j, a, b, jum, row, col;
char ch;

scanf ("%d\n", &cases);

for (ct = 0; ct < cases; ct++) {
i = 0; j = 0;
memset (data, 0, sizeof(char)*MAX*MAX);
ch = getchar();
while (!isalpha (ch)) ch = getchar();
while (1) {
if (isdigit (ch)) break;
if (isalpha (ch))
data[j++] = ch;
else if (ch == '\n') {
col = j;
j = 0;
i++;
}
ch = getchar();
}
row = i;
a = 0; b = 0;
while (1) {
if (ch == EOF) break;
if (ch == '\n') {
if ((a == 0) && (b == 0)) break;
memcpy (tempdata, data, sizeof(char)*MAX*MAX);
jum = 0;
if ((a >= 0) && (a < row) && (b >= 0) && (b < col))
if (data[a-1][b-1] == 'W')
flood_fill (a-1, b-1, row, col, &jum);
printf ("%d\n", jum);
a = 0; b = 0;
} else if (isdigit (ch)) {
if (a == 0)
a += (a*10) + (ch-'0');
else
b += (b*10) + (ch-'0');
}
ch = getchar();
}

if (cases-1 != ct) printf ("\n");
}
return 0;
}

[/c]

[jupiter777]

i can't find out whats the wrong with my code! plz help me with that.
here's my code:-
.............................................................................................................
#include<stdio.h>
#include<ctype.h>
#include<string.h>
long dr[8]={-1,-1,-1,0,0,1,1,1};
long dc[8]={-1,0,1,-1,1,-1,0,1};
void dfs_visit(long r, long c);
long valid(long r, long c);
long m,n,aa,p,q;
char grid[111][111];
long dfs(long n, long m){
long r,c,count=0;
if('W'==grid[n][m]){
aa++;
dfs_visit(n,m);
printf("%ld\n",aa);
}
else printf("0\n");
return count;
}
void dfs_visit(long r, long c){
long i,nr,nc,hh;
grid[r][c]='L';
for(i=0;i<8;i++){
nr=r+dr;
nc=c+dc;
hh=valid(nr,nc);
if((hh==1)&&('W'==grid[nr][nc])){
aa++;
dfs_visit(nr,nc);

} } }





long valid(long r, long c) {

if(r<0||c<0||r>=p||c>=q)return 0;
return 1;
}
int main(){
freopen("469.in","rt",stdin);
// freopen("oil.out","w",stdout);
long ss,dd,i=0,j,co,test,l,ff,k,r,c;
char ch,dummy[3],last[111];
scanf("%ld",&test);
for(dd=0;dd<test;dd++){
while(scanf("%s",&grid[0])==1){
aa=0;
i=1;
while(1){
scanf("%s",&grid);
if(isdigit(grid[0])){
p=i;
r=grid[0]-'0';
break;
}
i++;
}
aa=0;
q=strlen(grid[0]);
scanf("%ld",&c);
dfs(r-1,c-1);
if(aa>1)printf("%ld\n",aa);
else printf("0\n");
while(scanf("%ld%ld",&r,&c)==2){
aa=0;

q=strlen(grid[0]);
dfs(r-1,c-1);
if(aa>1) printf("%ld\n",aa);
else printf("0\n");
}
printf("\n");
}

}
return 0;
}

[Dominik Michniewski]

JUpiter - that's not forum for your questions .... please insert out questions into forums for apropriate set of problems , ok ?

Dominik

[jupiter777]

i can't find out whats the wrong with my code! plz help me with that.
here's my code:-
.............................................................................................................
#include<stdio.h>
#include<ctype.h>
#include<string.h>
long dr[8]={-1,-1,-1,0,0,1,1,1};
long dc[8]={-1,0,1,-1,1,-1,0,1};
void dfs_visit(long r, long c);
long valid(long r, long c);
long m,n,aa,p,q;
char grid[111][111];
long dfs(long n, long m){
long r,c,count=0;
if('W'==grid[n][m]){
aa++;
dfs_visit(n,m);
printf("%ld\n",aa);
}
else printf("0\n");
return count;
}
void dfs_visit(long r, long c){
long i,nr,nc,hh;
grid[r][c]='L';
for(i=0;i<8;i++){
nr=r+dr;
nc=c+dc;
hh=valid(nr,nc);
if((hh==1)&&('W'==grid[nr][nc])){
aa++;
dfs_visit(nr,nc);

} } }





long valid(long r, long c) {

if(r<0||c<0||r>=p||c>=q)return 0;
return 1;
}
int main(){
//freopen("469.in","rt",stdin);
// freopen("oil.out","w",stdout);
long ss,dd,i=0,j,co,test,l,ff,k,r,c;
char ch,dummy[3],last[111];
scanf("%ld",&test);
for(dd=0;dd<test;dd++){
while(scanf("%s",&grid[0])==1){
aa=0;
i=1;
while(1){
scanf("%s",&grid);
if(isdigit(grid[0])){
p=i;
r=grid[0]-'0';
break;
}
i++;
}
aa=0;
q=strlen(grid[0]);
scanf("%ld",&c);
dfs(r-1,c-1);
if(aa>1)printf("%ld\n",aa);
else printf("0\n");
while(scanf("%ld%ld",&r,&c)==2){
aa=0;

q=strlen(grid[0]);
dfs(r-1,c-1);
if(aa>1) printf("%ld\n",aa);
else printf("0\n");
}
printf("\n");
}

}
return 0;
}

[Moni]

you should also use the tags provided by this site:

Like:

[cpp]

#include<fstream>

[/cpp]

[razibcse]

I am getting Runtime error...
can't understand why?
is the process of my taking input is wrong?

Here's my code...

Code: Select all

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define MAX 120

long Q[MAX*MAX][2],r,c,nr,nc,i_max,j_max,head,tail;
long N,test,grid[MAX][MAX],visited[MAX][MAX];
char str[MAX][MAX];
long dr[]={0,-1,0,1,1,-1,1,-1};
long dc[]={-1,0,1,0,1,-1,-1,1};

void Insert_in_the_grid(long row,char string[]);
void find_result(long row,long col);
void main()
{

long i,j,flag,row,col,x,y;

char *ptr;
scanf("%ld\n",&N);
for(test=0;test<N;test++)
  {
  for(i=0;i<MAX;i++)
   for(j=0;j<MAX;j++)
     grid[i][j]=0;

  i=0;
  flag=0;
  while((ptr=gets(str[i]))!=0)
    {
    if(*ptr==NULL) break;
    if(isalpha(str[i][0]))
        Insert_in_the_grid(i,str[i]);
    else if(!isalpha(str[i][0]) && isdigit(str[i][0]))
        {
        if(!flag)
           {
           i_max=i;
           flag=1;
           }

        
        sscanf(str[i],"%ld %ld",&row,&col);
        if(row>i_max || col>j_max || row<1 || col<1)
           printf("0\n");
        else
          {
          if(grid[row-1][col-1]==0)
             printf("0\n");
          else if(grid[row-1][col-1]==1)
            {
            for(x=0;x<MAX;x++)
              for(y=0;y<MAX;y++)
                visited[x][y]=0;

            find_result(row-1,col-1);
            }
          }
        }
    i++;
    }

  printf("\n");
  }
}

void Insert_in_the_grid(long row,char string[])
{
long j;
j_max=strlen(string);
for(j=0;j<j_max;j++)
  {
  if(string[j]=='W')
    grid[row][j]=1;
  else if(string[j]=='L') grid[row][j]=0;
  }
}

void find_result(long row,long col)
{
long k;
head=tail=0;
Q[tail][0]=row;
Q[tail][1]=col;
visited[row][col]=1;
tail++;
while(head!=tail)
  {
  r=Q[head][0];
  c=Q[head][1];
  head++;
  for(k=0;k<8;k++)
     {
     nr=r+dr[k];
     nc=c+dc[k];
     if(nr>=0 && nr<i_max && nc>=0 && nc<j_max && grid[nr][nc]==1)
         if(visited[nr][nc]==0)
         {
         Q[tail][0]=nr;
         Q[tail][1]=nc;
         visited[nr][nc]=1;
         tail++;
         }
     }
  }


 printf("%ld\n",tail);
}

[losskid]

// i try many times but got wa who can help me
#include <iostream>
#include <stdio.h>
using namespace std;

char Land[110][110];
char templ[110][110];
int row,col;
char s[110];
int x,y;
int nLa;

void paint(int x,int y)
{
templ[x][y] = 'L';
nLa++;
if (templ[x+1][y]=='W'&&x+1>=0&&x+1<row&&y>=0&&y<col)
paint(x+1,y);
if (templ[x+1][y-1]=='W'&&x+1>=0&&x+1<row&&y-1>=0&&y-1<col)
paint(x+1,y-1);
if (templ[x+1][y+1]=='W'&&x+1>=0&&x+1<row&&y+1>=0&&y+1<col)
paint(x+1,y+1);
if (templ[x][y-1]=='W'&&x>=0&&x<row&&y-1>=0&&y-1<col)
paint(x,y-1);
if (templ[x][y+1]=='W'&&x>=0&&x<row&&y+1>=0&&y+1<col)
paint(x,y+1);
if (templ[x-1][y]=='W'&&x-1>=0&&x-1<row&&y>=0&&y<col)
paint(x-1,y);
if (templ[x-1][y-1]=='W'&&x-1>=0&&x-1<row&&y-1>=0&&y-1<col)
paint(x-1,y-1);
if (templ[x-1][y+1]=='W'&&x-1>=0&&x-1<row&&y+1>=0&&y+1<col)
paint(x-1,y+1);
}

void solve()
{
row++;
col = strlen(Land[0]);
nLa = 0;
int i,j;
for (i = 0;i<row;i++)
for (j = 0;j<col;j++)
templ[j] = Land[j];
if (templ[x-1][y-1] =='W')
paint(x-1,y-1);
cout << nLa << endl;
}

int main()
{
int nCase;
cin >> nCase;
cin.ignore(2);
for (int i = 0; i<nCase;i++){
row = -1;
while(gets(s)&&strlen(s)!=0)
{
if (sscanf(s,"%d %d",&x,&y)==2)
solve();
else{
row++;
strcpy(Land[row],s);
}
}
cout << endl;
}
return 0;
}

[minskcity]

Can anybody post some test cases for this problem or find an error in my code???
[cpp]#include <iostream>
#include <deque>
#include <string>
#include <vector>
#include <sstream>
#include <utility>
#include <fstream>
using namespace std;

const long dir[8][2] = {{1, 0}, {0, 1}, {1, 1},
{-1, -1}, {-1, 1}, {1, -1}, {0, -1}, {-1, 0}};

vector < string > data;
vector < pair < long, long > > visited;
pair < long, long > p;
long t, a, b;
long cnts[100][100];
string s;

inline bool good(const pair < long, long > &p){
return p.first > -1 && p.second > -1 &&
p.first < data.size() && p.second < data[0].size();
}

int main(){
// ifstream cin("in.txt");
cin >> t;
getline(cin, s);
getline(cin, s);
while(t--){
memset(cnts, 0, sizeof(cnts));

data.clear();
while(getline(cin , s) && (s[0] == 'W' || s[0] == 'L'))
data.push_back(s);

for(unsigned long i = 0; i < data.size(); i++)
for(unsigned long j = 0; j < data.size(); j++)
if(!cnts[j] && data[j] == 'W'){
long n = 0;
visited.clear();
deque < pair < long, long > > q;
q.push_back(make_pair(i, j));

while(q.size()){
p = q.front();
if(good(p) && !cnts[p.first][p.second] &&
data[p.first][p.second] == 'W'){
n++;
visited.push_back(p);
cnts[p.first][p.second] = 1;
for(long k = 0; k < 8; k++)
q.push_back(make_pair(p.first + dir[k][0], p.second + dir[k][1]));
}
q.pop_front();
}

for(unsigned long i = 0; i < visited.size(); i++)
cnts[visited.first][visited.second] = n;

}

do{
istringstream sin(s);
sin >> a >> b;
cout << cnts[a - 1] << endl;
}while(getline(cin, s) && s[0]);

if(t) cout << endl;
}

return 0;
}
[/cpp]