Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #106746

Re: Find the number of robots needed to walk through the rectangular grid

Show all headers | View raw

On Sat, Apr 9, 2016 at 8:18 AM, Joe <lildinho14@gmail.com> 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

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Find the number of robots needed to walk through the rectangular grid Joe <lildinho14@gmail.com> - 2016-04-09 07:18 -0700
  Re: Find the number of robots needed to walk through the rectangular grid Ian Kelly <ian.g.kelly@gmail.com> - 2016-04-09 10:43 -0600
    Re: Find the number of robots needed to walk through the rectangular grid Joe <lildinho14@gmail.com> - 2016-04-09 10:13 -0700
      Re: Find the number of robots needed to walk through the rectangular grid Dennis Lee Bieber <wlfraed@ix.netcom.com> - 2016-04-09 15:10 -0400
      Re: Find the number of robots needed to walk through the rectangular grid Mark Lawrence <breamoreboy@yahoo.co.uk> - 2016-04-09 20:23 +0100
        Re: Find the number of robots needed to walk through the rectangular grid Joe <lildinho14@gmail.com> - 2016-04-09 12:41 -0700
          Re: Find the number of robots needed to walk through the rectangular grid Mark Lawrence <breamoreboy@yahoo.co.uk> - 2016-04-09 20:55 +0100
            Re: Find the number of robots needed to walk through the rectangular grid Joe <lildinho14@gmail.com> - 2016-04-09 14:28 -0700

csiph-web