Posted: Sun Jun 10, 2007 3:12 am
Check your trace() procedure more carefully. It doesn't use variable m at all...
oh...k...got it
i used n instead of m...how cldn't i find it!!!!
thank u very much...
Page 2 of 3
Posted: Sun Jun 10, 2007 3:14 am
Posted: Fri Jul 06, 2007 12:32 am
Posted: 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.
"std::cin>>field;" needs space to put a terminating '\0' at the end of the line.
Posted: Fri Jul 06, 2007 12:48 am
woahhh.. thx
that was stupid of my...
that was stupid of my...
Posted: 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
Posted: Wed Aug 01, 2007 9:45 am
You should print 1.
----
Rio
----
Rio
Posted: 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]
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);
}
}
}
572 Oil Deposit.
Posted: 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;
}
572
Posted: Wed Jan 09, 2008 1:21 pm
There's no answer. I'm loosing all my spirits..
Posted: Wed Jan 09, 2008 5:29 pm
Well, here's a case for you:
Correct answer is 2.
Your problem is that your algorithm is just wrong.
Go and learn some graph theory, in particular DFS.
Code: Select all
5 5
@@@@@
**@**
@*@*@
@***@
@@@@@
0 0
Your problem is that your algorithm is just wrong.
Go and learn some graph theory, in particular DFS.
572 oil deposit
Posted: 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. 
Re: 572(oil deposit) TRICKY test case for you :-)
Posted: Thu May 01, 2008 4:23 pm
Friend, I didn't understand what you wanted to say!
Re: 572 WA :-(
Posted: 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;
}
}
Re: 572 WA :-(
Posted: 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.