572 - Oil Deposits

[theharshest]

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;
		cin>>m;
	}

}

[back_tracker]

easy problem, solve it using DFS

Hi,

This is an automated response from UVa Online Judge.

...Your submission with number 9066985 for the problem 572 - Oil Deposits has succeeded with verdict Accepted.

Congratulations! Now it is time to try a new problem.

Best regards,

The UVa Online Judge team

[@ce]

Getting WA...some test case plzzz

Code: Select all

AC

[brianfry713]

Code: Select all

2 1
*
@
0 0

[@ce]

Thanks brianfry713, i got my mistake.

[rifath_csedu]

I got WA in this problem... please give some test case

[brianfry713]

Input:

Code: Select all

9 1
@
@
@
@
*
*
*
@
*
10 6
*****@
@@@@*@
*@*@*@
**@**@
@@@@@*
**@@@@
*@@***
*@**@@
****@@
@@*@@*
7 6
@*@@**
**@@@@
@**@*@
@@*@**
*@***@
**@@**
*@*@@*
5 5
***@*
**@*@
@@@*@
*@*@@
****@
8 1
@
@
*
*
*
@
@
*
4 6
@*@@**
@****@
**@*@*
**@***
9 9
*@*@*@*@@
***@@@*@@
@@*@*@***
@@@@*@@*@
@*@@@**@*
@**@*@***
***@**@@*
*@@*@**@*
@@**@@@@*
4 5
*@@@*
@*@**
*@*@*
**@@*
7 9
@*@**@@@*
*@******@
@*@@***@*
****@@**@
**@@*@*@*
**@*@*@@@
*****@@@@
1 4
****
1 4
@**@
3 3
@@@
@@@
@@*
2 10
@@@**@@*@*
@*@@**@**@
4 10
@**@*@@**@
***@@**@@@
*@@@*@*@**
@*@*@@*@**
1 9
@@*@*@@@@
9 8
**@**@@@
@@@@@@*@
*@@@*@**
@*@@@*@*
*@@@**@*
*@*****@
**@@@*@@
*@@**@@@
*@@@*@*@
4 4
*@@@
@*@*
@@@@
@*@@
4 1
@
@
@
*
1 8
*@***@@@
7 5
*@***
**@**
***@*
*@***
*@@@*
*@**@
*@***
1 3
@@@
7 6
*@@@@@
**@**@
***@@@
@@***@
@**@*@
@**@**
**@*@*
2 10
@@**@@***@
@***@**@@@
6 4
*@@*
*@*@
@*@*
@@**
@**@
@**@
3 7
*@*@*@@
@@*@**@
@*@***@
3 8
@***@***
@*@@@@@@
@***@*@*
10 8
***@**@@
@@@**@@*
**@**@*@
@*@@***@
@@@@@@@@
*@@@*@@@
*@**@@*@
@*@*****
@**@@@@*
@@*****@
2 4
*@**
@*@*
6 1
@
*
*
@
*
@
2 7
@*@***@
@*@*@*@
5 3
**@
@@@
*@@
@**
**@
1 10
@@@**@@***
1 1
*
4 5
@@*@*
****@
@@*@@
@@@@*
9 10
@@@*@@@***
***@@@**@*
@@*@@*@@*@
@*@@@*@@@@
****@***@@
*@@@@@@*@*
*@@**@@*@@
*@@@*@*@*@
@@@@**@*@@
10 1
*
@
@
@
@
*
*
@
*
*
10 7
****@**
@***@@*
*@@****
@***@@@
*@@*@*@
@@*@@@*
@**@***
*@***@@
*@@**@@
*@@*@**
8 7
**@@*@*
@***@@@
@*@@@**
@@*@***
*@*@**@
@**@@@@
@@@@*@*
@@@@@**
3 9
@*@******
@@@*@@*@@
@*@**@*@*
8 5
*@*@*
**@@@
@@@@*
@@*@@
**@@*
***@*
@****
@@@*@
4 1
*
@
*
@
8 1
*
@
*
@
*
*
@
@
4 9
*@@**@*@@
*@*@@@*@*
*@@*@**@*
@@**@@@**
3 7
@@@@@@*
@**@@@@
*@@*@**
1 4
@*@@
9 7
@*@**@*
***@**@
*@@*@*@
*@**@@@
*@@**@@
@@**@**
*@@@@@*
@****@*
*@*@**@
2 1
@
*
5 8
@**@@*@@
@@@@**@@
@**@@@**
@@@@**@*
******@*
1 8
*@**@*@@
9 7
@**@**@
@**@@@*
****@@*
@****@@
*@@*@@*
**@@@*@
@**@*@*
****@@*
*@****@
2 6
@@*@@*
*@@@@@
9 6
***@@*
@***@@
@@@**@
*@@@@*
@@@@@*
**@@@*
@@@***
****@@
@@*@@*
9 3
*@*
**@
@@@
@*@
***
@@@
@*@
@@@
@*@
5 1
@
*
*
@
@
3 7
@@@@***
@@@@**@
@**@***
1 10
*@*@@*@@**
8 1
@
*
@
@
@
*
@
*
8 5
**@@@
*****
*@*@*
@@@**
@*@@*
@****
@*@@*
@@@@*
2 4
@***
*@@@
3 4
**@@
@@**
*@@@
8 9
@@@@@*@@@
******@*@
@@@@@@**@
@*@*@**@*
*@**@@**@
@@**@**@*
*****@@*@
*@*@*****
9 6
**@***
*@**@@
@*@@*@
*@****
*@@@@*
@**@@@
@*@*@@
*@**@*
***@*@
9 2
@*
@@
*@
*@
@*
@@
@@
*@
**
3 8
@**@*@@@
@@@**@*@
@*@@@@**
9 10
*@*@@@@@@*
@@**@*@@**
@*@****@@@
**@@@*@@*@
***@@**@*@
@@*@*@*@**
*@**@*@***
*@*@@*@*@*
*@*@@@@@**
7 2
*@
*@
*@
*@
*@
@@
*@
6 7
*@@@@@@
@@*@*@@
*@@*@@*
*@@***@
*****@*
*@@*@*@
8 5
@**@@
*@*@*
@@@*@
*@@@*
@@@@@
*@**@
@*@@@
@*@@@
7 6
@**@**
@*@@*@
@***@*
**@**@
@@*@@@
@@@***
@*@@@@
5 1
*
*
*
@
@
6 2
*@
@*
@@
@@
**
@*
2 4
@@*@
@*@@
9 4
@*@@
***@
**@@
*@@@
**@@
@@@@
@**@
****
@***
3 5
@**@*
*@@*@
**@*@
2 8
@@***@@*
@*@****@
2 7
@*@@*@*
@@@@*@*
6 10
@**@@**@@@
*@@@*@**@@
***@@**@@*
*@@@@@**@*
*@*@@*@*@*
@@@*@@@*@*
4 7
*@*@@@*
*@*****
@*@*@@*
****@@@
10 4
*@**
@@*@
***@
*@**
**@@
@***
@@**
@@@@
****
*@*@
3 7
@*@*@@*
*@*@*@*
*@@@@@@
10 8
****@***
@@****@@
**@@@*@@
*@@*@@**
*@@**@@*
@@******
*@******
**@***@@
**@**@@*
@**@*@*@
3 1
*
@
@
4 7
*******
*@@***@
@*@*@@@
@*@*@**
2 5
@***@
@@@**
4 1
@
@
*
@
2 10
@*@@***@*@
**@*******
9 2
@@
**
@@
**
@*
@@
@*
**
@*
4 6
@***@@
***@@@
@**@@@
*@@*@@
8 2
**
@@
@*
@*
@@
**
@*
@@
9 2
*@
**
@@
*@
@*
@*
**
@*
@@
1 1
@
1 2
*@
7 1
@
@
*
*
@
*
@
9 10
@*@@@***@*
*@@*@@@***
*@*@*@@*@*
**@***@*@*
@**@*@@**@
@@@@@*@@@*
@*@@****@@
@**@*@@@@*
@@*@@@**@@
3 9
*@*@*@@@@
@*@@@@@@@
*@**@**@@
9 10
@@*@*@@*@@
@@*@**@*@*
*@@@****@@
*@@@**@**@
***@*@****
@@@@@*@*@@
@*@@**@@@*
@*@*****@*
@**@*@****
8 6
@@@@*@
@@*@**
@*@*@@
@@*@**
@@@*@@
*@@*@*
*@*@**
**@*@@
10 10
@***@*@@@@
@*@@@*@***
*@@@*@*@@*
**@@@@*@@*
@*****@***
*@@***@@*@
*@**@@**@@
***@@@*@@@
****@@*@@@
*@*@**@***
9 10
@@@@@*@@@*
***@*@@*@*
**@**@@@**
@**@****@*
**@@**@@*@
*@@***@***
@****@*@@*
@*@@*@@*@*
******@*@*
4 9
@*@*@*@@@
@**@@*@**
*@@*@*@@@
@@**@@@@@
0 0

Ac output:

Code: Select all

2
3
4
1
2
4
3
1
1
0
2
1
3
2
3
1
1
1
2
2
1
3
3
2
2
2
1
1
3
4
2
2
0
2
1
2
3
1
3
3
2
3
1
1
2
3
1
1
3
4
1
3
2
2
2
3
3
2
1
1
4
1
1
1
2
1
2
1
2
1
2
1
3
1
2
2
2
3
6
1
4
1
2
2
2
4
4
2
2
3
1
1
3
2
1
4
2
3
3
1

[hello]

where's the problem;

Code: Select all

I got it

[uDebug]

brianfry713,
Thanks for the great test cases!

[fmmst]

Why runtime error

Code: Select all

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
#include <stdlib.h>
#include <stack>
#include <vector>
#include <queue>
#include <list>
#include <map>
#include <string>
#include <sstream>
#include <iostream>
#include <algorithm>

using namespace std;


void input();
void BFS(int index1,int index2);


char plot[102][102];
int row,clm;
int diraction1[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int diraction2[] = {-1, 0, 1, -1, 1, -1, 0, 1};

int main()
{
    input();

    return 0;
}

void input()
{
    int i,j,oil_polot;
    while(scanf("%d %d",&row,&clm)!=EOF)
    {
        if(row+clm==0) break;
        getchar();
        oil_polot=0;
        memset(plot,0,sizeof(plot));

        for(i=0;i<row;i++)
            gets(plot[i]);

        for(i=0;i<row;i++)
            for(j=0;j<clm;j++)
                if(plot[i][j]=='@')
                {
                    oil_polot++;BFS(i,j);
                }

        printf("%d\n",oil_polot);
    }
}

void BFS(int  index1,int index2)
{
    int temp1,temp2,i;
    queue<int>Q;

    Q.push(index1); Q.push(index2);
    while(!Q.empty())
    {
        temp1=Q.front(); Q.pop(); temp2=Q.front();Q.pop();
        for(i=0;i<8;i++)
        {
            index1=temp1+diraction1[i];
            index2=temp2+diraction2[i];

            if(plot[index1][index2]=='@')
            {
                plot[index1][index2]='*';
                Q.push(index1); Q.push(index2);
            }
        }
    }
}