10047 - The Monocycle

[Farid Ahmadov]

I am getting WA. Here some tests that I tried my progam on. Are these answers correct?

INPUT

Code: Select all

1 3
S#T
10 10
#S.......#
#..#.##.##
#.##.##.##
.#....##.#
##.##..#.#
#..#.##...
#......##.
..##.##...
#.###...#.
#.....###T
5 5
#S#..
#.#..
#.###
#...T
#####
10 10
S.........
..........
..........
..........
..........
..........
..........
..........
..........
........T.
3 3
ST#
##.
.#.
25 25
S........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
........................T
6 6
#.#...
#.S.#.
#####.
#..#..
#T##..
......
0 0

OUTPUT

Code: Select all

Case #1
destination not reachable

Case #2
minimum time = 49 sec

Case #3
minimum time = 17 sec

Case #4
minimum time = 30 sec

Case #5
minimum time = 14 sec

Case #6
minimum time = 55 sec

Case #7
minimum time = 30 sec

If these tests are correct please give me some other ones.
Thank you.

[Farid Ahmadov]

Hey People. Help. Won't anybody help me?

[Caesum]

my ac program gives the same output

[Farid Ahmadov]

Any I/O please.

[miras]

i keeps WA too.... it's terrible my code has 1000 ~lines


Can u give more tests....

[miras]

Yeah....

i got AC.

thanks to everyone....



it is not hard task....


Regards
MIras

[Renato]

Can anyone give me some ideas to solve this problem? Is this a graph problem, or geometric? Please help.

[jambon_vn]

As I think, this is a graph problem and you can use BFS to solve.

[asif_rahman0]

hello everybody,

i am having problem in description to get the idea. i dont get the following
lines:

Code: Select all

From any square either he moves forward to the next square or he remains in the same square but turns 90o left or right. Each of these actions requires exactly 1 second to execute. He always starts his ride facing north and with the mid

[mf]

Turning 90 degrees left means that you change north direction to west; west->south; south->east; east->north. In other words, if your direction vector is (dx, dy), then the new vector will be (-dy, dx).
Your position doesn't change.

Turning right is the opposite thing (north->east, east->south, etc.)

[asif_rahman0]

thnx mf.

[DD]

Hey People. Help. Won't anybody help me?

Maybe you can list your codes, and let us examine it for you.

[kbr_iut]

I tried a lot of times and generate many test cases and compare the output with uvatoolkit and mine but didnt fine any inconsistent......I am getting frequent WA...pliz anyone help.

Code: Select all

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define sz 30
#define inf 1<<30
const int X[4]={0,-1,0,1};
const int Y[4]={-1,0,1,0};
typedef struct st{int x,y,c,d;};
st v,var;
int tem,cost[sz][sz][4][5],x,y,t,txt,m,n;
char in[sz][sz];
bool check(){
	tem=cost[v.x][v.y][v.d][v.c];
	if(cost[var.x][var.y][var.d][var.c]<=tem+1)return false;
	cost[var.x][var.y][var.d][var.c]=tem+1;
}
bool forward(){
	var=v;
	var.x+=X[var.d];
	var.y+=Y[var.d];
	if(var.x>=m||var.x<0||var.y>=n||var.y<0)return false;
	if(in[var.x][var.y]=='#')return false;
	var.c=(var.c+1)%5;
	if(!check())return false;
}
bool left(){
	var=v;
	var.d=(var.d+3)%4;
	if(!check())return false;
}
bool right(){
	var=v;
	var.d=(var.d+1)%4;
	if(!check())return false;
}
int main(){
	int i,j,k,l,ans;
	//freopen("1.txt","r",stdin);
	while(cin>>m>>n&&(m||n)){
		for(i=0;i<m;i++){cin>>in[i];for(j=0;j<n;j++)if(in[i][j]=='S')v.x=i,v.y=j;}
		queue<st>q;
		v.c=1;v.d=1;
		for(i=0;i<sz;i++)for(j=0;j<sz;j++)for(k=0;k<4;k++)for(l=0;l<5;l++)cost[i][j][k][l]=inf;
		cost[v.x][v.y][v.d][v.c]=0;
		q.push(v);
		ans=inf;
		while(!q.empty()){
			v=q.front();q.pop();
			if(in[v.x][v.y]=='T'&&v.c==1){
				ans=cost[v.x][v.y][v.d][v.c];
				break;
			}
			if(forward())q.push(var);
			if(left())q.push(var);
			if(right())q.push(var);
		}
		if(txt++)cout<<endl;
		if(ans>=inf)cout<<"Case #"<<txt<<"\ndestination not reachable\n";
		else cout<<"Case #"<<txt<<"\nminimum time = "<<ans<<" sec\n";
	}
	return 0;
}

any help will be regarded gratefully.

[arash16]

Sample Input:

Code: Select all

5 10
.S........
..##.....#
..#...T...
..#.......
..#.......
15 15
S......#.......
.......#.......
......#.#....T.
......#..#.....
.....#...#.....
....#.....#...#
....#.#.#.#....
....#..#...#...
...#..##.#.#...
...#...#....#..
..#..#.#....#..
..#.#..#.....#.
.##..#.#.....#.
...#...#.....#.
#......#.......
1 10
.S.....T..
1 3
S#T
10 10
#S.......#
#..#.##.##
#.##.##.##
.#....##.#
##.##..#.#
#..#.##...
#......##.
..##.##...
#.###...#.
#.....###T
5 5
#S#..
#.#..
#.###
#...T
#####
10 10
S.........
..........
..........
..........
..........
..........
..........
..........
..........
........T.
3 3
ST#
##.
.#.
6 6
#.#...
#.S.#.
#####.
#..#..
#T##..
......
0 0

Sample Output:

Code: Select all

Case #1
minimum time = 19 sec

Case #2
minimum time = 82 sec

Case #3
minimum time = 13 sec

Case #4
destination not reachable

Case #5
minimum time = 49 sec

Case #6
minimum time = 17 sec

Case #7
minimum time = 30 sec

Case #8
minimum time = 14 sec

Case #9
minimum time = 30 sec

[kbr_iut]

thanx "arash16" for ur kind help.
but unfortunately my WA code produces same output.
I tested with a lot of randomly generated cases and compared with uvatoolkit.com.but in every case i got same output.