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 -- https://mail.python.org/mailman/listinfo/python-list
