1
$\begingroup$

You are given a 2d grid where each grid item has a value of 1 or 0, you can only move horizontally or vertically and if both blocks have value of 1. You are also given a starting index, the output should have the "connected" grid items property to true.

For example:

input = [
  [{value: 0}, {value: 1}, {value: 1}],
  [{value: 0}, {value: 0}, {value: 1}],
  [{value: 1}, {value: 1}, {value: 1}]
];

startRowIndex = 2;
startColumnIndex = 0;

output = [
  [{value: 0}, {value: 1, connected: true}, {value: 1, connected: true}],
  [{value: 0}, {value: 0}, {value: 1, connected: true}],
  [{value: 1, connected: true}, {value: 1, connected: true}, {value: 1, connected: true}]
];

}

This is the first part of the question, this can be easily solved using either DFS or BFS.

The second part is you are given the output of the first function and the same start indices. Along with these two input arguments, you are also given a flipIndex. The grid item at the given flip index will have the value flipped. Now give the updated matrix with the updated "connected" path.

input = [
  [{value: 0}, {value: 1, connected: true}, {value: 1, connected: true}],
  [{value: 0}, {value: 0}, {value: 1, connected: true}],
  [{value: 1, connected: true}, {value: 1, connected: true}, {value: 1, connected: true}]
];

startRowIndex = 2;
startColumnIndex = 0;

flipRowIndex = 1;
flipColumnIndex = 2;

output = [
  [{value: 0}, {value: 1}, {value: 1}],
  [{value: 0}, {value: 0}, {value: 0}],
  [{value: 1, connected: true}, {value: 1, connected: true}, {value: 1, connected: true}]
];

Is there an effective algorithm to solve the above problem?

$\endgroup$
  • $\begingroup$ Is there an algorithm to solve the second questions without resetting the grid. I was thinking of writing different cases for the flipped grid item however it is not elegant. $\endgroup$ – Bobby Feb 9 at 20:24
  • $\begingroup$ Can you credit the source where you originally encountered this problem? $\endgroup$ – D.W. Feb 9 at 22:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.