10358 - Matrix

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

Moderator: Board moderators

Post Reply
Rivaldo
New poster
Posts: 19
Joined: Sun Jul 07, 2002 3:59 pm

10358 - Matrix

Post by Rivaldo »

Can I solve it like this :
First calc both "my" and agents' min-dist to all the girds from own position, then compare the dist. If "mine" is shorter than two agents', "I" can escape. Otherwise, "I" may be eliminated or trapped in the Matrix.

I think it may be right. But it got WA.

Picard
Learning poster
Posts: 96
Joined: Mon Jun 24, 2002 1:22 pm
Location: Hungary
Contact:

Post by Picard »

what if trinity's path is not shorter? she may still escape (first example below). this algorithm takes only a little closer to the solution (when you can escape for sure, because you are closer to a phone as any agent), but how do you solve the problem in all other cases? (how do you know if you are eliminated or trapped?)

input:

Code: Select all

2
...P..##
M..#.A##
...P..##
########
########
########
########
#######A

A.######
.M######
########
########
########
########
########
#####P#A
output:

Code: Select all

You can escape.
You are trapped in the Matrix.

Rivaldo
New poster
Posts: 19
Joined: Sun Jul 07, 2002 3:59 pm

Post by Rivaldo »

Emm~, I changed my algorithm.
First, I use three loops to find the best position for both "I" and agents.
[pascal]
noe := true;
for i := 1 to 32 do if dist[m, i] < 100 then begin
now := true;
for j := 1 to 32 do if (i <> j) and (dist[a1, j] < 100) and (dist[a1, i] > dist[m, i]) then
for k := 1 to 32 do if (k <> i) and (dist[a2, k] < 100) and (dist[a2, i] > dist[m, i]) then
begin
now := true;
for p := 1 to ph do
if dist[i, pho[p]] <= min(dist[j, pho[p]], dist[k, pho[p]]) then
now := false;
if now then break;
end;
noe := now;
if not noe then break;
end;
[/pascal]

If no-escaped and only one agent is reachable, I will check if there is any circle in graph. If exist, "I" will be trapped, otherwise I will be caught by agents.
If no-escaped and two agent can be reachable, I will be caught.

I want to know whether it's correct. (Unfortunely I got WA again and again)

Picard
Learning poster
Posts: 96
Joined: Mon Jun 24, 2002 1:22 pm
Location: Hungary
Contact:

Post by Picard »

sorry i can't help in this. i used kinda bruteforce (there are not too many states on a given board)

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:

Post by Yarin »

That looks correct although I prefer to use the evaluation symbols +1 (Good Guy win), 0 (draw) and -1 (Bad Guys win) all the time and not +1 if the guy to move will win whether or not he is Good or Bad (I think that is more confusing).

The graph does contain loops which is why you must search backwards. Start with the final states (when good guy reaches telephone or when he is caught by an agent) and work with it's neighbouring states in the way you describe. Repeat this until you've filled all states. Note that you don't have to care about the draw states; these will simple never be filled in the search algorithm above.

A forward searching algorithm is futile!!

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:

Post by Yarin »

That input is draw, that is correct.

I start by looping through all 2*32*32*32 states (at least half the squares are filled with #) and mark any state with M at a phone as a win and M at an A as a loss (in case of both of these at the same square, it doesn't matter since this position isn't reachable, the game would be over the previous move).

Then I do a loop like this:

do
loop through all states
if Good Guys to move:
if a neighbouring node is +1, make this node +1
if all neighbourings nodes are -1, make this node -1
if Bad Guys to move:
if a neighbouring node is -1, make this node -1
if all neighbouring nodes are +1, make this node +1
end loop
while new nodes are being updated

This is not the fastest solution by far, but it's fast enough for this problem and it is easy to code!

Maniac
Experienced poster
Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland

Post by Maniac »

Hi,

I keep getting WA for this problem. Could somebody help me out? For simplicity I'll name the person in the matrix who's trying to escape Neo :-).

Here's my idea:
1. determine whether Neo can escape. If so, we're done. If not:
2. determine whether Neo is eliminated. If so, we're done. If not, Neo is trapped.

Approach of 1:
There are n possible positions for Neo and the agents (3<=n<=32). I Keep a 3D array for all n^3 situations, where the first index is the position of Neo, the second of agent1 and the third of agent3:

turns[j][k] = the minimal number of turns needed for Neo to escape from this situation (or -1 if impossible)

Then I set array-values to 1 for all situations where Neo is directly next to a vacant phone and Neo isn't on the same position as an agent.

Then I work out

Code: Select all

int t = 1
while(there is a situation for which it takes t turns for Neo to escape) {
    t++;
    try for all unescaped situations whether Neo can escape from that situation in t turns
}
Determining whether Neo can escape from a situation in t turns is done as follows:

Neo can escape in t turns if there is at least one move he can make such that for all possibles moves the agents make, the new situation is such that Neo can escape from that one in t-1 turns or less.

Approach of 2:
In almost the same way I determine from which situations Neo is eliminated. This time:

turns[j][k] = the minimal number of turns needed for the agents to eliminate Neo (or -1 if impossible)

and

Neo is eliminated in t turns if for all moves he can make, there is at least one move of the two agents together, such that the new situation is such that Neo is eliminated from that one in t-1 turns or less.

If anyone can spot a flaw in my aproach or have a better idea, please let me know! I'm pretty desparate by now...

Thanks, Erik

Maniac
Experienced poster
Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland

Post by Maniac »

Could somebody please post the correct results for the following test cases?
Thanks, Erik

Code: Select all

30
########
#...A..#
#.####.#
#.#M.#.#
#P#..#P#
#.####.#
#...A..#
########

#######A
####M###
###...##
#......#
#......#
#...A..#
#PPPPPP#
########

#######A
####M###
####.###
#......#
#......#
#...A..#
#PPPPPP#
########

#######A
#M#..###
#.#..###
#.#..###
#.#..###
#P...###
#A...###
########

########
#M.#.A.#
#..#P.P#
#.######
#A.....#
#......#
#......#
########

########
#M.#.A.#
#..#P.P#
#.######
#.....A#
#......#
#P.....#
########

########
#M.....#
#.######
#.#A####
#..##A##
##..#.##
###..P##
########

########
#M.....#
#..#####
#.#A####
#..##A##
##..#.##
###..P##
########

########
########
########
########
########
##A..###
##PM.###
#######A

########
########
########
########
########
##A..###
##P.M###
#######A

########
########
########
########
########
##A.####
##P.M###
#######A

########
########
########
########
########
##A#####
##P.M###
#######A

###A####
##.#.###
#..#..##
P..#..P#
#.....##
##...###
###M####
###....A

###A####
##...###
#.....##
P.....P#
#.....##
##...###
###M####
####...A

###A####
##...###
#.....##
P.....P#
#.....##
##...###
###M####
###....A

M#...#A#
##.P.###
#.....##
#......#
########
#####A##
#...####
########

#MA#####
########
###P####
########
#####A##
########
########
########

...P..##
M..#.A##
...P..##
########
########
########
########
#######A

A.######
.M######
########
########
########
########
########
#####P#A

.A######
.M######
########
########
########
########
########
#####P#A

#####.##
#####.##
#####.##
AA.M...P
#####.##
#####.##
#####.##
#####.##
.
########
#..P...#
#.####.#
#P#M.#P#
#.####.#
#..P...#
#A....A#
########
.
########
#.A#####
#.######
#..M...#
#.####.#
#.####.#
#....A##
########

########
########
########
#A.M...#
######.#
#.####.#
#....A##
########

########
#...A.P#
#.######
#..M...#
#.####.#
..####..
#....A.#
########

########
########
########
#..M...#
#.......
#P.....P
#A..P..A
########

########
########
########
#..M...#
#.......
#P.....P
#A.....A
########

########
########
########
#..M...#
#.......
#......P
#A.....A
########

#.A.A.##
..#.#..#
.##P##.#
P##.##P#
.......#
#.....##
##.M.###
########

#.A.A.##
..#.#..#
.##.##.#
P##.##P#
.......#
#.....##
##.M.###
########


little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

Here it is:

Code: Select all

You are trapped in the Matrix.
You are trapped in the Matrix.
You are eliminated.
You are eliminated.
You are trapped in the Matrix.
You can escape.
You are eliminated.
You are trapped in the Matrix.
You can escape.
You are trapped in the Matrix.
You are trapped in the Matrix.
You are eliminated.
You can escape.
You are trapped in the Matrix.
You are eliminated.
You are trapped in the Matrix.
You are eliminated.
You can escape.
You are trapped in the Matrix.
You are trapped in the Matrix.
You can escape.
You are trapped in the Matrix.
You are eliminated.
You are eliminated.
You are eliminated.
You can escape.
You are trapped in the Matrix.
You are trapped in the Matrix.
You are eliminated.
You are eliminated.
But you have two stray dots inbetween cases. After removing the dots, my output is:

Code: Select all

You are trapped in the Matrix.
You are trapped in the Matrix.
You are eliminated.
You are eliminated.
You are trapped in the Matrix.
You can escape.
You are eliminated.
You are trapped in the Matrix.
You can escape.
You are trapped in the Matrix.
You are trapped in the Matrix.
You are eliminated.
You can escape.
You are trapped in the Matrix.
You are eliminated.
You are trapped in the Matrix.
You are eliminated.
You can escape.
You are trapped in the Matrix.
You are trapped in the Matrix.
You can escape.
You are trapped in the Matrix.
You are eliminated.
You are eliminated.
You are eliminated.
You can escape.
You are eliminated.
You are eliminated.
You can escape.
You are eliminated.

Maniac
Experienced poster
Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland

Post by Maniac »

sorry about the extra dots. I took your second output and it matched with my output. So I still haven't found an error :-(

Could somebody perhaps have a look at my code? Any help is welcome!
Thanx, Erik

[java]got AC.

What I corrected:
- set turns to zero for the situations where Neo can escape in 0 turns
- Neo is not eliminated in a situation if he can escape from that situation!
[/java]

Post Reply

Return to “Volume 103 (10300-10399)”