OJ Board

Posted: **Thu Sep 14, 2006 4:42 am**

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

Posted: **Thu Sep 14, 2006 7:59 pm**

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

Posted: **Fri Dec 19, 2008 10:27 pm**

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

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

Posted: **Fri Dec 19, 2008 10:36 pm**

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

btw: the above steps are correct..

Posted: **Tue Aug 17, 2010 9:03 am**

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

Posted: **Sat Apr 30, 2011 5:18 am**

* 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~

Posted: **Thu Feb 09, 2012 2:29 am**

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

OJ Board

676 - Horse Step Maze

Re: 676 - Horse Step Maze

Re: 676 - Horse Step Maze

676 - Horse Step Maze

Re: 676 - Horse Step Maze

Re: 676 - Horse Step Maze