On 09/04/2016 18:13, Joe wrote:
On Saturday, 9 April 2016 18:44:20 UTC+2, Ian wrote:
On Sat, Apr 9, 2016 at 8:18 AM, Joe wrote:
How to find the number of robots needed to walk through the rectangular grid
The movement of a robot in the field is divided into successive steps
In one step a robot can move either horizontally or vertically (in one row or
in one column of cells) by some number of cells
A robot can move in one step from cell X to cell Y if and only if the distance
between the centers of the cells X and Y is equal to the sum of integers
contained in X and Y
Cell X is reachable for robot A if either A is currently standing in the cell X
or A can reach X after some number of steps. During the transfer the robot can
choose the direction (horizontal or vertical) of each step arbitrarily
[![enter image description here][1]][1]
I started implementing it by first checking the row and print the index of the
Cell X and Y where the distance is equal to the sum of integers contained in X
and Y
but after coding I found it difficult to remember the index when moving
vertically
So I thought to Build a graph where nodes are grid cells and edges are legal
direct movements, then run any connected components algorithm to find which
cells are reachable from each other
Can anyone implement it with graphs or queue?
I'd use a disjoint-set data structure. The number of robots needed is
equal to the number of disjoint subsets.
https://en.wikipedia.org/wiki/Disjoint-set_data_structure
Could you post a formal solution of disjoint-set using my algorithm
You write the code, we comment on it. No code, no comment. Got the
message?
--
My fellow Pythonistas, ask not what our language can do for you, ask
what you can do for our language.
Mark Lawrence
--
https://mail.python.org/mailman/listinfo/python-list
