572

mf · Post by mf » Sun Jun 10, 2007 3:12 am

Check your trace() procedure more carefully. It doesn't use variable m at all...

soddy · Post by **soddy** » Sun Jun 10, 2007 3:14 am

oh...k...got it
i used n instead of m...how cldn't i find it!!!!

thank u very much...

O_Maago · Post by **O_Maago** » Fri Jul 06, 2007 12:32 am

well, I still am getting WA... little help please

Code: Select all


REMOVED

mf · Post by mf » Fri Jul 06, 2007 12:45 am

Increase the size of your 'field' array.
"std::cin>>field;" needs space to put a terminating '\0' at the end of the line.

O_Maago · Post by **O_Maago** » Fri Jul 06, 2007 12:48 am

woahhh.. thx

that was stupid of my...

chetan · Post by **chetan** » Wed Aug 01, 2007 8:34 am

for the following i/p should i print 1 or 0 ???

Code: Select all

1 1
@
0 0

rio · Post by **rio** » Wed Aug 01, 2007 9:45 am

You should print 1.

----
Rio

gaucho.andre · Post by **gaucho.andre** » Fri Aug 31, 2007 11:16 pm

After the first WA, I've debugged the program and now all inputs I can think about return correct answers. Can someone help me find out what's wrong? PS: Java solution.

Code: Select all

import java.io.IOException;
import java.util.StringTokenizer;

class Main {
	
	static char[][] field;
	static short[][] groups;
	static boolean end = false;
	static short count;
	
	static String ReadLn (int maxLg)
	{
        byte lin[] = new byte [maxLg];
        int lg = 0, car = -1;

        try
        {
            while (lg < maxLg)
            {
                car = System.in.read();
                if ((car < 0) || (car == '\n')) break;
                lin [lg++] += car;
            }
        }
        catch (IOException e)
        {
            return (null);
        }

        if ((car < 0) && (lg == 0)) return (null);  // eof
        return (new String (lin, 0, lg));
    }
	
	static void input(){
		
		String input, linha;
		StringTokenizer st;
		short m, n;
			
			input = ReadLn(255);
			st = new StringTokenizer(input);
			m = Short.parseShort(st.nextToken());
			if(m == 0) {
				end = true;
				return;
			}
			n = Short.parseShort(st.nextToken());
		
			field = new char[m][n];
			groups = new short[m][n];
			for(short i = 0; i < m; i++){
			
				linha = ReadLn(255);
				field[i] = linha.toCharArray();	
			}
	}

	static void check(int p, int q){
		
		short num = groups[p][q];
		try{if((field[p-1][q-1] == 64)&&(groups[p-1][q-1] == 0)){groups[p-1][q-1] = num; check(p-1,q-1);}}
			catch(Exception e){}
		try{if((field[p-1][q] == 64)&&(groups[p-1][q] == 0)){groups[p-1][q] = num; check(p-1,q);}}
			catch(Exception e){}
		try{if((field[p-1][q+1] == 64)&&(groups[p-1][q+1] == 0)){groups[p-1][q+1] = num; check(p-1,q+1);}}
			catch(Exception e){}
		try{if((field[p][q-1] == 64)&&(groups[p][q-1] == 0)){groups[p][q-1] = num; check(p,q-1);}}
			catch(Exception e){}
		try{if((field[p][q+1] == 64)&&(groups[p][q+1] == 0)){groups[p][q+1] = num; check(p,q+1);}}
			catch(Exception e){}
		try{if((field[p+1][q-1] == 64)&&(groups[p+1][q-1] == 0)){groups[p+1][q-1] = num; check(p+1,q-1);}}
			catch(Exception e){}
		try{if((field[p+1][q] == 64)&&(groups[p+1][q] == 0)){groups[p+1][q] = num; check(p+1,q);}}
			catch(Exception e){}
		try{if((field[p+1][q+1] == 64)&&(groups[p+1][q+1] == 0)){groups[p+1][q+1] = num; check(p+1,q+1);}}
			catch(Exception e){}	
	}

	public static void main(String[] args){
		
		while(true){
			
			input();
			if(end) break;
			
			count = 0;
			for(short i = 0; i <groups.length; i++){
				for(short j = 0; j < groups[i].length; j++){
					
					if(field[i][j] == 64){
						if(groups[i][j] == 0){
							groups[i][j] = ++count;
							check(i,j);
						}
					}
				}
			}
			
			System.out.println(count);
		}
	}
}

[/code]

linux · Post by **linux** » Mon Dec 10, 2007 11:55 am

I'm getting Wrong Answer in this problem. I couldn't figure out what the problem is! Can you help me?

Code: Select all

#include<iostream>
#include<cstdio>
using namespace std;

bool mat[105][105];

int main () {
	int m, n, i, j;

	bool get_oil_deposit (int *row, int* col);
	void print_result(int *row, int* col);

	while (get_oil_deposit(&m, &n)) {
		for (i=0;i<m;i++) {
			for (j=0;j<n;j++) {
				if (mat[i][j] == true) {
					if (i +1 <= m && j>=1 && mat[i + 1] [j - 1] == true) {
						if ((i+1 <= m && j+1<=n && mat[i + 1][j+1]==true) || (j+1 <= n && mat[i][j+1] == true)) {
							mat[i+1][j] = true;
							mat[i][j] = false;
						}
						else
							mat[i][j] = false;
					}
					else if ((i+1 <= m && mat[i+1][j]==true) || (i+1<=m && j+1<=n && mat[i+1][j+1]==true) || (j+1<=n && mat[i][j+1]==true)) {
						mat[i][j] = false;
					}
				}
			}
		}

		if (m &&n)
			print_result (&m, &n);
	}

	return 0;
}

bool get_oil_deposit (int *row, int* col) {
	scanf("%d %d", row, col);
	char ch;

	if (*row) {
		for (int i=0;i<*row;i++) {
			for (int j=0;j<*col;)
				if ((ch = getchar()) == '@' || ch=='*') {
					if (ch=='@') {
						mat[i][j] = true;
						j++;
					}
					else if (ch == '*') {
						mat[i][j] = false;
						j++;
					}
				}
		}
		return true;
	}
	else
		return false;
}


void print_result(int *row, int* col) {
	int sum_dep = 0,i,j;

	for (i=0;i<*row;i++) {
		for (j=0;j<*col;j++) {
			sum_dep += (int) mat[i][j];
		}
	}
	cout<<sum_dep<<endl;
}

linux · Post by **linux** » Wed Jan 09, 2008 1:21 pm

There's no answer. I'm loosing all my spirits..

mf · Post by mf » Wed Jan 09, 2008 5:29 pm

Well, here's a case for you:

Code: Select all

5 5
@@@@@
**@**
@*@*@
@***@
@@@@@
0 0

Correct answer is 2.

Your problem is that your algorithm is just wrong.
Go and learn some graph theory, in particular DFS.

linux · Post by **linux** » Thu Jan 24, 2008 10:21 am

Thanks very much to figure out my problem. After knowing that I tried usign recursion and it's accepted. Thanks again.

tiagowanderley · Post by **tiagowanderley** » Thu May 01, 2008 4:23 pm

Friend, I didn't understand what you wanted to say!

theharshest · Post by **theharshest** » Mon Jan 12, 2009 12:26 am

I am getting WA for the following code.. Please help.. !!!

Code: Select all

#include<iostream>
#include<string>
#include<vector>
#include<utility>
#include<stack>
using namespace std;

int main()
{
	int m,n,c=0,x,y;
	vector< vector<bool> > vb;
	vector<string> v;
	string st;
	pair<int,int> pii,tmp1,tmp2;
	stack< pair<int,int> > s;

	cin>>m;	

	while(m!=0)
	{
		c=0;
		cin>>n;
		v.clear();
		vb.resize(m);

		for(int i=0;i<vb.size();i++)
			vb[i].resize(n,0);

		
		for(int i=0;i<m;i++)
		{
			
				cin>>st;
				v.push_back(st);
			
		}
		
		for(int i=0;i<m;i++)
		{
			for(int j=0;j<n;j++)
			{	
				//cout<<i<<" "<<j<<endl;					
				//cout<<"hi"<<endl;
				if(v[i][j]=='@' && vb[i][j]==0)
				{
					pii.first=i;
					pii.second=j;

					s.push(pii);

					while(!s.empty())
					{
						tmp1=s.top();
						s.pop();
						x=tmp1.first;
						y=tmp1.second;
						vb[x][y]=1;		
						
	    if(x-1>=0 && v[x-1][y]=='@' && vb[x-1][y]==0)
            {   
                tmp2.first=x-1;
                tmp2.second=y;
                s.push(tmp2);                           
            }
            if(y-1>=0 && v[x][y-1]=='@' && vb[x][y-1]==0)
            {   
                tmp2.first=x;
                tmp2.second=y-1;
                s.push(tmp2);                           
            }
            if(x-1>=0 && y-1>=0 && v[x-1][y-1]=='@' && vb[x-1][y-1]==0)
            {   
                tmp2.first=x-1;
                tmp2.second=y-1;
                s.push(tmp2);                           
            }
            if(x+1<m && y+1<n && v[x+1][y+1]=='@' && vb[x+1][y+1]==0)
            {   
                tmp2.first=x+1;
                tmp2.second=y+1;
                s.push(tmp2);                           
            }
            if(x+1<m && v[x+1][y]=='@' && vb[x+1][y]==0)
            {   
                tmp2.first=x+1;
                tmp2.second=y;
                s.push(tmp2);                           
            }
            if(y+1<n && v[x][y+1]=='@' && vb[x][y+1]==0)
            {   
                tmp2.first=x;
                tmp2.second=y+1;
                s.push(tmp2);                           
            }
            if(x+1<m && y-1>=0 && v[x+1][y-1]=='@' && vb[x+1][y-1]==0)
            {   
                tmp2.first=x+1;
                tmp2.second=y-1;
                s.push(tmp2);                           
            }
            if(x-1>=0 && y+1<n && v[x-1][y+1]=='@' && vb[x-1][y+1]==0)
            {   
                tmp2.first=x-1;
                tmp2.second=y+1;
                s.push(tmp2);                           
            }
			
					}
			c++;
				}
			}		
		}
		cout<<c<<endl;#include<iostream>
#include<string>
#include<vector>
#include<utility>
#include<stack>
using namespace std;

int main()
{
	int m,n,c=0,x,y;
	vector< vector<bool> > vb;
	vector<string> v;
	string st;
	pair<int,int> pii,tmp1,tmp2;
	stack< pair<int,int> > s;

	cin>>m;	

	while(m!=0)
	{
		c=0;
		cin>>n;
		v.clear();
		vb.resize(m);

		for(int i=0;i<vb.size();i++)
			vb[i].resize(n,0);

		
		for(int i=0;i<m;i++)
		{
			
				cin>>st;
				v.push_back(st);
			
		}
		
		for(int i=0;i<m;i++)
		{
			for(int j=0;j<n;j++)
			{	
				//cout<<i<<" "<<j<<endl;					
				//cout<<"hi"<<endl;
				if(v[i][j]=='@' && vb[i][j]==0)
				{
					pii.first=i;
					pii.second=j;

					s.push(pii);

					while(!s.empty())
					{
						tmp1=s.top();
						s.pop();
						x=tmp1.first;
						y=tmp1.second;
						vb[x][y]=1;		
						
	    if(x-1>=0 && v[x-1][y]=='@' && vb[x-1][y]==0)
            {   
                tmp2.first=x-1;
                tmp2.second=y;
                s.push(tmp2);                           
            }
            if(y-1>=0 && v[x][y-1]=='@' && vb[x][y-1]==0)
            {   
                tmp2.first=x;
                tmp2.second=y-1;
                s.push(tmp2);                           
            }
            if(x-1>=0 && y-1>=0 && v[x-1][y-1]=='@' && vb[x-1][y-1]==0)
            {   
                tmp2.first=x-1;
                tmp2.second=y-1;
                s.push(tmp2);                           
            }
            if(x+1<m && y+1<n && v[x+1][y+1]=='@' && vb[x+1][y+1]==0)
            {   
                tmp2.first=x+1;
                tmp2.second=y+1;
                s.push(tmp2);                           
            }
            if(x+1<m && v[x+1][y]=='@' && vb[x+1][y]==0)
            {   
                tmp2.first=x+1;
                tmp2.second=y;
                s.push(tmp2);                           
            }
            if(y+1<n && v[x][y+1]=='@' && vb[x][y+1]==0)
            {   
                tmp2.first=x;
                tmp2.second=y+1;
                s.push(tmp2);                           
            }
            if(x+1<m && y-1>=0 && v[x+1][y-1]=='@' && vb[x+1][y-1]==0)
            {   
                tmp2.first=x+1;
                tmp2.second=y-1;
                s.push(tmp2);                           
            }
            if(x-1>=0 && y+1<n && v[x-1][y+1]=='@' && vb[x-1][y+1]==0)
            {   
                tmp2.first=x-1;
                tmp2.second=y+1;
                s.push(tmp2);                           
            }
			
					}
			c++;
				}
			}		
		}
		cout<<c<<endl;
		cin>>m;
	}

}
		cin>>m;
	}

}

Chirag Chheda · Post by **Chirag Chheda** » Tue Jan 13, 2009 3:14 pm

Can you please post only one code. There are 2 codes in it. Try using floodfill in it. It would become much easier.

OJ Board

572 - Oil Deposits

572 Oil Deposit.

572 oil deposit

Re: 572(oil deposit) TRICKY test case for you :-)

Re: 572 WA :-(

Re: 572 WA :-(