Oct 2010
1 / 9
Oct 2010
Oct 2010
aseempandey
Oct '10

I don't know if this is the correct place to post this. Anyways, i am trying to solve this problem hosted on acmicpc live archives and getting WA.
Please point out the flaw in my logic. I am doing a dfs and storing all the paths in string vector.

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2004
Problem code-2004
Problem name-Fire Trucks

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
using namespace std;
vector<string>out;
bool check(int i,string path){
    int s=path.length();
    for ( int t=0;t<s;++t)
        if ( path[t]-'0'==i)
            return false;
    return true;
}
void dfs(int ar[21][21],int root,int final,string path){
        
    char ch=root+'0';
    path=path+ch;
    
    if ( root==final){
        out.push_back(path);
        return ;
    }

    for ( int i=1;i<21;++i){
        string tmp(path);
        if ( ar[root][i]==1 && check(i,path))
            dfs(ar,i,final,tmp);
    }
}
int main(){
    int final;
    scanf("%d",&final);
    int ar[21][21]={0};
    int a,b;
    while(scanf("%d %d",&a,&b),a+b>0){
        ar[a][b]=1;
        ar[b][a]=1;
    }
    string path="";
path.reserve(20);
dfs(ar,1,final,path);

int outs=out.size();
sort(out.begin(),out.end());
for ( int i=0;i<outs;++i){
    int ws=out[i].length();
    for ( int j=0;j<ws;++j)
        printf("%c ",out[i][j]);
    printf("\n");
}

printf("\n");
return 0;
}

  • created

    Oct '10

  • last reply

    Oct '10
  • 8

    replies

  • 505

    views

  • 2

    users

  • 1

    link

leppyr64
Oct '10

You need to read the problem statement.

aseempandey
Oct '10

I am still getting WA. I have changed the code a little bit where it was wrong earlier.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
using namespace std;
vector<string>out;
bool check(int i,string path){
    int s=path.length();
    for ( int t=0;t<s;++t)
        if ( path[t]-'A'==i-1)
            return false;
    return true;
}
void dfs(int ar[21][21],int root,int final,string path){
        char ch=root+'A'-1;
    path=path+ch;
   

    if ( root==final){
        out.push_back(path);
        return ;
    }

    for ( int i=1;i<21;++i){
        string tmp(path);
        if ( ar[root][i]==1 && check(i,path))
            dfs(ar,i,final,tmp);
    }
}
int main(){
    int final;
    scanf("%d",&final);
    int ar[21][21]={0};
    int a,b;
    while(scanf("%d %d",&a,&b),a+b>0){
        ar[a][b]=1;
        ar[b][a]=1;
    }


string path="";
path.reserve(20);
dfs(ar,1,final,path);

int outs=out.size();
sort(out.begin(),out.end());
for ( int i=0;i<outs;++i){
    int ws=out[i].length();
    for ( int j=0;j<ws;++j)
        printf("%d ",out[i][j]-'A'+1);
    printf("\n");
}

printf("\n");
return 0;
}
leppyr64
Oct '10

That appears correct. Does that website check for whitespace at the end of the line?

3
1 2
2 3

Your code outputs: "1 2 3 "
The judge might expect: "1 2 3"

Try that and see if it works.

leppyr64
Oct '10

And the final extra newline character you have as well?

2
1 2
0 0
2 
1 2
0 0

Your output:

1 2 
1 2

Expected:

1 2
1 2
aseempandey
Oct '10

how could i know which dataset is the final one.
According to sample input, i gather that an input file can only have 1 dataset. Their sample input mentions nothing like
input number of test cases first, then other things.

leppyr64
Oct '10

Oh, that's why the wrong answer. Silly me. You need to read until scanf for final returns EOF.

int x;
while(scanf("%d", &x) != EOF)
{
// do stuff
}
aseempandey
Oct '10

thanks. i am still getting 'presentation error' but that at least means my output is correct, just the format is not matching. smile
thanks again.

Suggested Topics

Want to read more? Browse other topics in Off-topic or view latest topics.