676 - Horse Step Maze

[daveon]

Well, all the different kinds of IO have been covered here. If you email me your code, I can take a look.

[Mohammad Mahmudur Rahman]

Thanks for your concern. I'm mailing the code to you. Please have a look...

[newkid]

hi,
can anyone post the number of steps required for the following input set..

Code: Select all

6

(2,2)
(1,1)

(8,6)
(9,7)

(8,3)
(9,4)

(9,9)
(1,1)

(1,1)
(9,9)

(8,4)
(9,5)

I get:

Code: Select all

DEBUG_LINE: steps : 1000030 (more than 50000) 

DEBUG_LINE: steps : 809897 (more than 50000)

DEBUG_LINE: steps : 4713

DEBUG_LINE: steps : 88

DEBUG_LINE: steps : 16

DEBUG_LINE: steps : 29957

[newkid]

got it acc..
i made stupidest mistake .. grrh

btw: the above steps are correct..

[ytlau9]

Please help!! I cant figure out why i got WA! could anyone give some I/O case??

Code: Select all

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<utility>
#include<algorithm>
using namespace std;

int tmp=0,count2=0,found=0,v[11][11];
pair <int,int> path[50001];

void dfs(int xi, int yi,int xe, int ye){
        v[xi][yi] = 1;
        count2++;
        path[tmp++] = make_pair(xi,yi);
        if(found) return;
        if(count2-1>50000 || (xi==xe && yi==ye)){found=1; return;}
        if(!v[xi-1][yi+1]&& !found){
                dfs(xi-1,yi+1,xe,ye);
                path[tmp++] = make_pair(xi,yi);
        }
        if(!v[xi+1][yi+1]&&!found){
                dfs(xi+1,yi+1,xe,ye);
                path[tmp++] = make_pair(xi,yi);
        }
        if(!v[xi+1][yi-1]&&!found){
                dfs(xi+1,yi-1,xe,ye);
                path[tmp++] = make_pair(xi,yi);
        }
        if(!v[xi-1][yi-1]&&!found){
                dfs(xi-1,yi-1,xe,ye);
                path[tmp++] = make_pair(xi,yi);
        }
        if(!found) {v[xi][yi]=0;count2++;}
}
void print(int xi, int yi, int xe, int ye){
        for(int i=0;i<count2-1;i++)
                printf("(%d,%d), ",path[i].first,path[i].second);
        printf("(%d,%d)\n", path[count2-1].first, path[count2-1].second);
}

int main(){
        int xi,yi,xe,ye,n;
        char c[10];
        scanf("%d", &n);
        while(n--){
                found=tmp=0;
                count2=0;
                memset(v,0,sizeof(v));
                for(int i=0; i<=10;i++){
                        v[i][0] = 1;
                        v[0][i] = 1;
                        v[i][10] = 1;
                        v[10][i] = 1;
                }
                scanf("%s",c);
                xi = c[1] -'0';
                yi = c[3] -'0';
                scanf("%s",c);
                xe = c[1] -'0';
                ye = c[3] -'0';
                if((xe+ye-xi-yi) %2 !=0) printf("fail\n");
                else dfs(xi,yi,xe,ye);

                if(count2-1>50000) printf("more than 50000 steps\n");
                else {print(xi,yi,xe,ye);}

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

[suneast]

* Wow, this problem is really my nightmare
*
* "If the number of steps is over 50000 print `more than 50000 steps'."
* at first, I miss this sentence and got a dozen of WA...
*
* I try to store the answer as ANSWER[size++]=(...)
* then I check size>50000, but it's quite wrong
* because the horse only go sz-1 steps!
* so I have to change it like this size-1>50000
* poor
*
* "Print a blank line between datasets."
* at last, another dozen of WA because of this sentence...
* maybe UVa online judge is a little too strict about PE and WA
*
* finally got ac...
*
* maybe next time, I need to be more careful about this kind of problem
*
* happy coding~

[brianfry713]

input:

Code: Select all

3

(1,1)
(9,9)

(1,1)
(3,1)

(1,1)
(2,1)

output from my AC program:

Code: Select all

(1,1), (2,2), (1,3), (2,4), (1,5), (2,6), (1,7), (2,8), (1,9), (2,8), (3,9), (4,8), (5,9), (6,8), (7,9), (8,8), (9,9)

(1,1), (2,2), (1,3), (2,4), (1,5), (2,6), (1,7), (2,8), (1,9), (2,8), (3,9), (4,8), (5,9), (6,8), (7,9), (8,8), (9,9), (8,8), (9,7), (8,6), (7,7), (6,6), (5,7), (4,6), (3,7), (4,6), (5,5), (6,4), (7,5), (8,4), (9,5), (8,4), (9,3), (8,2), (7,3), (6,2), (5,3), (4,4), (3,5), (4,4), (3,3), (4,2), (5,1), (4,2), (3,1)

fail