10358  Matrix
Moderator: Board moderators
10358  Matrix
Can I solve it like this :
First calc both "my" and agents' mindist 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.
First calc both "my" and agents' mindist 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.
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:
output:
input:
Code: Select all
2
...P..##
M..#.A##
...P..##
########
########
########
########
#######A
A.######
.M######
########
########
########
########
########
#####P#A
Code: Select all
You can escape.
You are trapped in the Matrix.
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 noescaped 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 noescaped 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)
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 noescaped 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 noescaped 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)
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!!
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!!
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!
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!
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 arrayvalues 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
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 t1 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 t1 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
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 arrayvalues 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
}
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 t1 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 t1 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
Could somebody please post the correct results for the following test cases?
Thanks, Erik
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.###
########

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
Here it is:
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 trapped in the Matrix.
You are trapped in the Matrix.
You are eliminated.
You are eliminated.
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.
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]
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]