Link to the problem on UVa Online Judge
For this problem imagine of an imaginary person that is walking on the grid and always is searching for the next character of the text message and when he is standing on the character that he seeks for he presses "select" button. Can you define the state of this person? What are the characteristics of this persons situation? Of course the row and the column he is standing on and the character of the text message he is trying to match next. What can he do when he is in state (row, column, index)? If the character at mat[row][col] is equal to the character at textMessage[row][column] then he can go to the state (row, column, index+1) with cost of cost(row, column, index) + 1, which means an stroke that helps him to go from state (row, column, index) to state (row, column, index+1).
What other options he has when he is in state (row, column, index), he can move left, right, up or down which yields to a new state (newRow, newColumn, index) which means still searching for the index character of text message but in a new position on the grid.
This is actually the definition of Breadth First Search algorithm which is one of the most popular algorithms of Graph Theory.
The hidden part of the solution is (newRow, newColumn) when the person chooses to go left, right, up or down. If the person chooses to move in one direction when would he end up? This can also be precalculated (like the following image) and be used in BFS.
For this problem imagine of an imaginary person that is walking on the grid and always is searching for the next character of the text message and when he is standing on the character that he seeks for he presses "select" button. Can you define the state of this person? What are the characteristics of this persons situation? Of course the row and the column he is standing on and the character of the text message he is trying to match next. What can he do when he is in state (row, column, index)? If the character at mat[row][col] is equal to the character at textMessage[row][column] then he can go to the state (row, column, index+1) with cost of cost(row, column, index) + 1, which means an stroke that helps him to go from state (row, column, index) to state (row, column, index+1).
What other options he has when he is in state (row, column, index), he can move left, right, up or down which yields to a new state (newRow, newColumn, index) which means still searching for the index character of text message but in a new position on the grid.
This is actually the definition of Breadth First Search algorithm which is one of the most popular algorithms of Graph Theory.
The hidden part of the solution is (newRow, newColumn) when the person chooses to go left, right, up or down. If the person chooses to move in one direction when would he end up? This can also be precalculated (like the following image) and be used in BFS.
No comments:
Post a Comment