469 - Wetlands of Florida

All about problems in Volume 4. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
vahid sanei
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

Re: Wetlands Of Florida - 469

Post by vahid sanei » Sat Feb 21, 2009 6:03 pm

To frandres
I think you should use BFS instead of recursive method for this problem
and you get Run Time error with this code because in your code you dont allocate space for your string

Code: Select all

      string position;
      position[0] = grid[grid.size()-1][0];
      position[1] = ' ';
      position[2] = grid[grid.size()-1][2];
it`s better

Code: Select all

     
      string position;
      position.resize(3);
      position[0] = grid[grid.size()-1][0];
      position[1] = ' ';
      position[2] = grid[grid.size()-1][2];
Impossible says I`m possible

fkrafi
New poster
Posts: 13
Joined: Wed Sep 15, 2010 1:36 pm

Re: Wetlands Of Florida - 469

Post by fkrafi » Tue Mar 29, 2011 8:49 pm

Why WA!!!!!

Code: Select all

#include<stdio.h>
#include<string>
#include<string.h>
#include<algorithm>
using namespace std;
typedef pair<int, int> pii;
#define SZ 1000

char grid[SZ][SZ], s[SZ];
char seen[SZ][SZ];
int len[SZ], sz, cnt;
int dr[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dc[] = {-1, 0, 1, -1, 1, -1, 0, 1};

int isNum(char ch)
{
	return (ch>='0' && ch<='9');
}

void set()
{
	int i, j;
	for(i=1; i<=sz; i++)
		for(j=0; j<len[i]; j++)
			seen[i][j+1] = grid[i][j];
}

void dfs(pii u)
{
	cnt++;
	seen[u.first][u.second] = 'L';
	pii v;
	int i;
	for(i=0; i<8; i++)
	{
		v.first = u.first + dr[i];
		v.second = u.second + dc[i];
		if(v.first<1 || v.second<0 || v.first>sz || v.second>=len[v.first])continue;
		if(seen[v.first][v.second]=='W')
			dfs(v);
	}
}

void input()
{
	int r, c, l, i;
	pii u;
	sz = 0;
	while(gets(s))
	{
		if( isNum(s[0]) )break;
		if(s[0]=='L' || s[0]=='W')
		{
			strcpy(grid[++sz], s);
			len[sz] = strlen(s);
		}
	}
	do{
		if( !isNum(s[0]) )break;
		i = cnt = r = c = 0;
		l = strlen(s);
		while(i<l && isNum(s[i]))
		{
			r = r*10 + s[i]-48;
			i++;
		}
		while( !isNum(s[i]) )i++;
		while(i<l && isNum(s[i]))
		{
			c = c*10 + s[i]-48;
			i++;
		}
		u.first = r;
		u.second = c;
		set();
		if(seen[u.first][u.second]=='W' && u.first>=1 && u.first<=sz && u.second>=1 && u.second<=len[u.first])
			dfs(u);
		printf("%d\n", cnt);
	}while(gets(s));

}

int main()
{
	int t, flag = 0;
	scanf("%d", &t);
	while(t--)
	{
		if(flag)printf("\n");
		flag = 1;
		input();
	}
	return 0;
}

rij
New poster
Posts: 5
Joined: Mon Nov 03, 2008 3:59 am
Location: BD
Contact:

Re: Wetlands Of Florida - 469

Post by rij » Wed Aug 03, 2011 4:04 pm

Me getting errors :( . Why?? Please someone tell me what is the problem? Thanks in advance.

Code: Select all

Got ac problem was in I/O format :)

User avatar
mahade hasan
Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm
Location: University of Rajshahi,Bangladesh

Re: Wetlands Of Florida - 469

Post by mahade hasan » Mon Oct 08, 2012 9:28 pm

Cutt....After ACC
I m great fool..........
anyway thanks a lot brainfry
Last edited by mahade hasan on Wed Oct 10, 2012 6:32 pm, edited 1 time in total.
we r surrounded by happiness
need eyes to feel it!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: Wetlands Of Florida - 469

Post by brianfry713 » Tue Oct 09, 2012 10:15 pm

Try input:

Code: Select all

1

LLLLLLLLL
LLWWLLWLL
LWWLLLLLL
LWWWLWWLL
LLLWWWLLL
LLLLLLLLL
LLLWWLLWL
LLWLWLLLL
LLLLLLLLL
3 2
3 2
Check input and AC output for thousands of problems on uDebug!

User avatar
enamsustcse
New poster
Posts: 9
Joined: Fri May 04, 2012 9:41 pm
Location: SUST, Sylhet, Bangladesh
Contact:

Re: Wetlands Of Florida - 469

Post by enamsustcse » Sun Feb 03, 2013 2:52 pm

I am getting WA!
please, help me.... :x :x :x

here is m code:

Code: Select all

#include <iostream>
#include <queue>
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
int bfs (int x, int y);
string graph[99];
string ex[99];
int n,m;
int main()
{
    int t, caseno=1,x,y, i;
    string in, a, b;
    char abc[1000];
    string::size_type sz;
    cin>>t;
    cin>>in;
    while(t--)
    {
        graph[0] = in;
        for (i = 1; 1; i++)
        {
            cin>>in;
            if(toupper(in[0])>='A'&&toupper(in[0])<='Z') graph[i] = in;
            else break;
        }
        m = graph[0].size();
        n = i;
        strcpy(abc,in.c_str());
        do
        {
//            cout<<in<<"::"<<y<<endl;
            in = abc;
            for (i=0; i<n; i++)
                ex[i] = graph[i];
            if(toupper(in[0])>='0'&&toupper(in[0])<='9')
            {
                x = atoi(in.c_str());
                cin>>y;
//                cout<<in<<":@:"<<y<<endl;
                cout<<bfs(x-1,y-1)<<endl;
            }
            else break;
//            cout<<<<":"<<endl;
        }
        while(scanf("%s", abc)==1);
        cout<<endl;
    }
    return 0;
}

int bfs (int x, int y)
{
    if(x<=n&&y<=m&&ex[x][y]=='W')
    {
        queue <int> q;
    q.push(x);
    q.push(y);
    int cnt=0;
    while(!q.empty())
    {
        int i, j;
        int u = q.front();
        q.pop();
        int v = q.front();
        q.pop();
        cnt++;
        ex[u][v]='L';
        for (i=u-1; i<=u+1; i++)
        {
            for (j=v-1; j<=v+1; j++)
            {
                if(i>=0&&j>=0&&i<n&&j<m)
                {
                    if(ex[i][j]=='W')
                    {
                        ex[i][j]='L';
                        q.push(i);
                        q.push(j);
                    }
                }
            }
        }
    }

    return cnt;
    }
    else return 0;

}
-----
Enamul Hassan,
Student,
2nd year, CSE,
SUST, Sylhet, Bangladesh

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: Wetlands Of Florida - 469

Post by brianfry713 » Mon Feb 04, 2013 11:36 pm

The outputs of two consecutive cases will be separated by a blank line. Don't print an extra blank line at the end.
Check input and AC output for thousands of problems on uDebug!

User avatar
enamsustcse
New poster
Posts: 9
Joined: Fri May 04, 2012 9:41 pm
Location: SUST, Sylhet, Bangladesh
Contact:

Re: Wetlands Of Florida - 469

Post by enamsustcse » Tue Feb 05, 2013 10:05 am

brianfry713 wrote:The outputs of two consecutive cases will be separated by a blank line. Don't print an extra blank line at the end.
Thanks a lot once more... :) :) :)
-----
Enamul Hassan,
Student,
2nd year, CSE,
SUST, Sylhet, Bangladesh

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: Wetlands Of Florida - 469

Post by brianfry713 » Mon Oct 07, 2013 11:31 pm

Input:

Code: Select all

2

LLLLLLLLL
LLWWLLWLL
LWWLLLLLL
LWWWLWWLL
LLLWWWLLL
LLLLLLLLL
LLLWWLLWL
LLWLWLLLL
LLLLLLLLL
3 2
3 2

LLLLLLLLL
LLLLLLLLL
LWLLLLLLL
LLWWLWWLL
LLLWWWLLL
LLLLLLLLL
LLLWWLLWL
LLWLLLLLL
LLLLLLLLL
3 2
7 5
AC output:

Code: Select all

12
12

8
3
Check input and AC output for thousands of problems on uDebug!

shuvokr
Learning poster
Posts: 66
Joined: Tue Oct 02, 2012 8:16 pm
Location: Bangladesh

Re: Wetlands Of Florida - 469

Post by shuvokr » Tue Oct 22, 2013 5:19 pm

@triplemzim
1

LLLLLLLLL
LLWWLLWLL
LWWLLLLLL
LWWWLWWLL
LLLWWWLLL
LLLLLLLLL
LLLWWLLWL
LLWLWLLLL
LLLLLLLLL
3 2 (press enter and you will get result)
7 5 (press enter and you will get result)
(press enter and your input is terminated)

Code: Select all

enjoying life ..... 

triplemzim
New poster
Posts: 48
Joined: Sat Apr 06, 2013 6:02 pm

Re: Wetlands Of Florida - 469

Post by triplemzim » Wed Oct 23, 2013 8:21 pm

Code: Select all

AC :)
thanks, shuvokr and brianfry713
the most important thing is that after the last case there is no blank line. so you have to terminate that program when EOF reached... :)
Last edited by triplemzim on Wed Oct 23, 2013 9:51 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: Wetlands Of Florida - 469

Post by brianfry713 » Wed Oct 23, 2013 8:53 pm

Try the I/O I posted in this thread.
Check input and AC output for thousands of problems on uDebug!

walking_hell
New poster
Posts: 14
Joined: Tue Sep 24, 2013 4:35 pm

uva 469

Post by walking_hell » Thu Dec 19, 2013 2:52 am

why RE !!!

Code: Select all

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
using namespace std;
int tot;
string field[110];
int i;
string fild[110];
int dfs(int x,int y)
{
    if(fild[x][y]=='W')
    tot++;
    fild[x][y]='L';
    for(int l=-1;l<=1;l++)
    for(int j=-1;j<=1;j++)
    {

        if(x+l<0 || x+l>=i||y+j<0 || y+j>=fild[0].length()||fild[x+l][y+j]!='W')
        continue;
        dfs(x+l,y+j);

    }
}
int main()
{
    int test;

    //freopen("/media/Others/input.txt","r",stdin);

    cin>>test;
    getchar();
    getchar();
    int flg=0;
    for(int ll=0;ll<test;ll++)
        {

            int flag=0;
            char ara[110];
            int l=0;
            if(flg!=0)
            cout<<endl;
            flg=1;
            while(gets(ara) && strcmp(ara,""))
            {


                //cout<<ara;
                if(ara[0]=='L'|| ara[0]=='W')
                {field[l]=ara;
                l++;}
                if((ara[0]!='L'&&ara[0]!='W')&&flag==0)
                {i=l;
                flag=1;}
                if(ara[0]!='L'&& ara[0]!='W')
                {
                    int row,col;


            sscanf(ara,"%d %d",&row,&col);
            for(int m=0;m<i;m++)
            fild[m]=field[m];
            int res=dfs(row,col);
            cout<<tot<<endl;
            tot=0;

            }

          }
       }
    return 0;
}

just_yousef
New poster
Posts: 50
Joined: Tue Dec 17, 2013 11:01 pm

Re: Wetlands Of Florida - 469

Post by just_yousef » Fri Jan 03, 2014 2:03 am

hi..
can any tell me why im I getting WA !! :( :(

Code: Select all

AC :D 

????????
New poster
Posts: 5
Joined: Mon Nov 11, 2013 7:00 pm

Re:

Post by ???????? » Fri Jan 03, 2014 6:15 pm

Saul Hidalgo wrote:Hi! Test with this cases:

Code: Select all

2

LLLLLLLLL
LLWWLLWLL
LWWLLLLLL
LWWWLWWLL
LLLWWWLLL
LLLLLLLLL
LLLWWLLWL
LLWLWLLLL
LLLLLLLLL
3 2
7 5

LLLLLLLLL
LLWWLLWLL
10 2
7 5
The correct output is:

Code: Select all

12
4

0
0
You code have

Code: Select all

12
4

0
2
I hope that is help you.
i think your input is not valid..in problem statement it is clearly stated that "Given the row and column number of a grid cell that contains water" & i also got ac while my code gives wrong answer for your last test case

Post Reply

Return to “Volume 4 (400-499)”