10358 - Matrix

Rivaldo · Post by **Rivaldo** » Fri Sep 20, 2002 5:19 pm

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 · Post by **Picard** » Fri Sep 20, 2002 6:08 pm

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 · Post by **Rivaldo** » Tue Sep 24, 2002 1:53 pm

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 · Post by **Picard** » Tue Sep 24, 2002 2:06 pm

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

Yarin · Post by **Yarin** » Sun Oct 13, 2002 8:07 pm

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 · Post by **Yarin** » Mon Oct 14, 2002 5:12 pm

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 · Post by **Maniac** » Thu Sep 02, 2004 5:21 pm

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 · Post by **Maniac** » Fri Sep 03, 2004 12:58 am

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 · Post by **little joey** » Fri Sep 03, 2004 8:23 am

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 · Post by **Maniac** » Fri Sep 03, 2004 10:33 am

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]