Find the number of robots needed to walk through the rectangular grid
Joe
lildinho14 at gmail.com
Sat Apr 9 15:41:56 EDT 2016
On Saturday, 9 April 2016 21:24:02 UTC+2, Mark Lawrence wrote:
> 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
Sorry, I was desperate
I deleted the post
More information about the Python-list
mailing list