10047 - The Monocycle

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

corns
New poster
Posts: 2
Joined: Wed Apr 22, 2009 4:25 pm

Re: 10047 - The Monocycle

Post by corns » Mon May 18, 2009 6:09 am

I have tried this serval hours, and finally got AC.

Believe it or not, what I discovered is that:
it seems that some of the test cases contain muliple TARGET 'T', and the judge only accept solution handling the latest Target.

Hope this can help

millan
New poster
Posts: 1
Joined: Wed May 26, 2010 9:11 am

Re: 10047 - The Monocycle

Post by millan » Wed May 26, 2010 10:42 am

don't print a blank line at the end of the last case, or the judge will give a result of WA instead of PE, which cost me long time to debug.
any other, try the case below if you use a BFS method:

Code: Select all

4 7
##....T
##.###.
S..###.
##.....
0 0
the output should be

Code: Select all

Case #1
minimum time = 14 sec
hope it helps

mohamed90
New poster
Posts: 2
Joined: Mon Aug 02, 2010 7:59 pm

Re: 10047 - The Monocycle

Post by mohamed90 » Mon Aug 02, 2010 8:06 pm

please anyone help me and trace any case because i didn't know how i will count the time

case like this

2 2
S.
#T


or

3 2
.S
..
T#

free
New poster
Posts: 6
Joined: Fri Aug 13, 2010 8:35 am
Location: China

10047 The Monocycle,,help me !!

Post by free » Thu Sep 09, 2010 6:49 pm

Hi, i tested a lot of testcases and got the same as its output.but when i submit,it always WA. i am puzzling...

can anyone give me some hard testcase or help me find out my wrong place? thx .

this is my code, you can test the datas with it can find out my wrong place? thx .

Code: Select all

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<ctype.h>
#include<iostream>
using namespace std;
#define MAX1 30
#define MAX2 25000
int n,m;
int sx,sy,ex,ey;
char map[MAX1][MAX1];
bool vis[MAX1][MAX1][5][5];
int sec[MAX1][MAX1][5][5];
int dirx[5]={0,-1,0,1,0};
int diry[5]={0,0,-1,0,1};

void getin()
{
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++) cin>>map[i][j];
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            if (map[i][j] == 'S') {sx=i; sy=j;}
            else if (map[i][j] == 'T') {ex=i; ey=j;}  
//    memset(sec,0,sizeof(sec));
    for (int i=0;i<=MAX1-1;i++)
        for (int j=0;j<=MAX1-1;j++)
            for (int k=0;k<=4;k++)
                for (int t=0;t<=4;t++) sec[i][j][k][t]=0;
    memset(vis,false,sizeof(vis));
}

void bfs()
{
    int front, rear;
    int qx[MAX2] ,qy[MAX2], dir[MAX2], col[MAX2], fa[MAX2];
    front=rear=1;
    qx[1]=sx; qy[1]=sy; dir[1]=1; col[1]=0; vis[sx][sy][0][1]=true; sec[sx][sy][0][1]=0; 
    fa[1]=0;
    while (front <= rear)
    {
        for (int k=-1;k<=2;k++) {
            int i=dir[front]+k;
            if (i<1) i=4; 
            else if (i>4) i=i-4;
            if (i != dir[front])
            {
                int x=qx[front];
                int y=qy[front];
                int z=col[front];
                if (!vis[x][y][z][i])
                {
                    rear++;
                    qx[rear]=x; qy[rear]=y; col[rear]=z; dir[rear]=i;   
                    vis[x][y][z][i]=true;
                    fa[rear]=front;
                    if ((dir[front]==3 && i==1) || (dir[front]==4 && i==2) || (i==3 && dir[front]==1) || (i==4 && dir[front]==2))
                        sec[x][y][z][i]=sec[qx[front]][qy[front]][col[front]][dir[front]]+2;
                    else
                        sec[x][y][z][i]=sec[qx[front]][qy[front]][col[front]][dir[front]]+1; 
                }
            }
            else if (i == dir[front])
            {
                int x=qx[front]+dirx[i];
                int y=qy[front]+diry[i];
                int z=(col[front]+1)%5;
                if (x>=1 && x<=n && y>=1 && y<=m && map[x][y]!='#' && !vis[x][y][z][i])
                {
                    rear++;
                    qx[rear]=x; qy[rear]=y; col[rear]=z; dir[rear]=i;
                    vis[x][y][z][i]=true;
                    fa[rear]=front;
                    sec[x][y][z][i]=sec[qx[front]][qy[front]][col[front]][dir[front]]+1;
                }
            }
        }
        front++;
    }
    int min=0;
    int ok=0;
    for (int j=1;j<=4;j++) if (sec[ex][ey][0][j] > 0) 
    {
        if (min==0) min=sec[ex][ey][0][j];
        else if (min>0 && sec[ex][ey][0][j] < min) min=sec[ex][ey][0][j];
        ok=1;
    }
    if (ok)
        printf("minimum time = %d sec\n",min);
    else 
        printf("destination not reachable\n");
}

int main()
{
    freopen("10047.in","r",stdin);
    freopen("10047.out","w",stdout);
    int count=0;
    cin>>n>>m;
    while (n != 0)
    {
        if (count) cout<<endl;
        printf("Case #%d\n",count+1);
        getin();
        bfs();
        cin>>n>>m;
        count++;
    }
    return 0;
}

jenovano2sko
New poster
Posts: 5
Joined: Tue Oct 19, 2010 8:07 am

Re: 10047 - The Monocycle

Post by jenovano2sko » Mon Nov 15, 2010 9:41 am

Are you allowed to run over the destination square without green touching it and count it as an action, or is the destination square forbidden until you get the green on it?

Also,
i have confirmed what someone else posted above:

::WARNING:: THERE ARE, IN FACT, MULTIPLE DESTINATION SQUARES. How do I know this, you ask? I got a WA, so I added a flag to tell me when I have scanned the character 'T' more than once in a given grid. When I hit T the second time, I exit with an error. Upon resubmitting this code, I got RTE.

I'm not sure how to handle this in my program. He said "pick the farthest," but I'm not sure what that means. The one that it takes the longest to get to? The longest manhattan distance from the source? The longest euclidean distance?

I can't stand how they give you puzzles that you can't solve unless you figure out that they give you dirty input and add code to get around it. It's not fair.

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 10047 - The Monocycle

Post by Obaida » Sat Dec 11, 2010 2:30 am

I would like to clear a point about this problem.
There will be only one S and one T for every test and you need to find out minimum time required to go form S to T.

Input

Code: Select all

4 7
##....T
##.###.
S..###.
##.....
4 7
##.....
##.###.
S..###.
##....T
0 0
Output

Code: Select all

Case #1
minimum time = 14 sec

Case #2
minimum time = 22 sec
>>hope this helps those, who are getting WA
try_try_try_try_&&&_try@try.com
This may be the address of success.

Post Reply

Return to “Volume 100 (10000-10099)”