0
$\begingroup$

For the next problem I can not think of how to find a solution with graph searches (I thought it was backtracking but my college professor told me that I should use graph searches, which I do not know much about, to solve it).

As input we obtain a matrix (3x4) of connections ("|" or "-") which we must decode in the least amount of movements, to avoid that the bomb explodes. As an output inform one of the possible solutions.

The decoding consists in that the matrix must contain only characters "-". To achieve this they tell us that if we move an element of the matrix, both the values ​​of the column and row of the matrix change. For example if I move the element (0,0) of the matrix in this case the "-" change to "|" and vice versa in the column 0 and row 0. In the image (where (1) represents the input matrix and (2) the decoded matrix) a solution to inform would be:

move (0,3) and then (2,1)

enter image description here

How to design an algorithm that solves this problem without using backtracking directly?

$\endgroup$
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – dkaeae May 14 at 7:10
1
$\begingroup$

"Graph search" is a very general term that includes breadth-first-search and depth-first-search. Let's say you wanna do BFS on this problem.

For this problem, think of a matrix, or a state, as a node in the graph. The pseudocode might look like this:

  • Push the "input node" into a queue.
  • While desired output node is not found:
    • Pop an element from the queue
    • Go through all the "moves" that could be done on that node. For a 3x4 matrix there would be 12 possible moves.
    • Push the results of each move into the queue.

Hope this helps!

$\endgroup$
  • $\begingroup$ thanks for your help. What you are referring to is that I have to see the entire matrix as a node, ie: 1- at the beginning the queue has a (node = array) 2- When pop a (node = matrix) and all its subnodes are "-", stop the algorithm 3- then for each move of a subnode of the node (to which pop applies), I put that new matrix in the queue. 4- In the end I will have a queue with many (nodes = matrix) Anyway, when I get to step 2-, how will I have memorized the nodes that I moved? Does this ensure me the minimum of movements in any case? $\endgroup$ – FredieF May 15 at 16:53
  • $\begingroup$ To keep track of the steps you can put in another "field." So your node would now be a struct (dict) with two fields. One is the matrix, and the other would be a list of steps (coordinates) that get you to that point. Breadth first search ensures shortest path when a graph has no loop and is unweighted. See here google.com/url?sa=t&source=web&rct=j&url=https://… $\endgroup$ – Art May 16 at 0:08

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.