10047 - The Monocycle

[corns]

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]

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]

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]

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]

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]

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