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?
Input
4 6
3 1 3 2 0 0
1 3 2 1 2 1
3 3 1 0 1 2
1 2 0 2 3 3
Output
6
My code so far
def row_walk(inputstring):
inputs = inputstring.split(" ")
row_number, column_number = int(inputs[0]), int(inputs[1])
matrix = [list(map(int, input().split())) for _ in range(row_number)]
matrix_transposed = (np.transpose(matrix)).tolist()
used = set()
for i, r1 in enumerate(matrix[0]):
for j, r2 in enumerate(matrix[0]):
if j > i and r1+r2 == j-i:
used.update((i, j))
cell_movement = [x for x in range(len(matrix[0])) if x not in used]
trivial_cell = [y for y in range(len(matrix[0])) if y in used]
return cell_movement, trivial_cell
if __name__=="__main__":
print(row_walk(input()))
--
https://mail.python.org/mailman/listinfo/python-list
