Fire Trucks [ hosted on acmicpc live archive ]

[aseempandey]

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

[leppyr64]

You need to read the problem statement.

Street intersections are identified by positive integers not more than 20, with the firestation always at intersection 1.

[aseempandey]

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]

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.

[aseempandey]

still WA.

[leppyr64]

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]

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]

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]

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