Question

his is a function problem. You only need to complete the function maxCities() that take a 2-d vector of char, m, n as parameters and returns the maximum number of spiritual cities geek can travel. The driver code automatically appends a new line. Constraints: 1. 1 <= T <= 100 2. 1 <= N, M <= 102 Example: Input: 2 5 5 ....* ..... ..*.. ..... ..... 1 2 ** Output: 10 0 Explanation: Testcase 1: (1, 4), (2, 2), (2, 3), (2, 4), (2, 5), (3, 2), (3, 4), (4, 2), (4, 3), (4, 4) are the spiritual cities which geek will visit.

Answer 1

I am currently trying to use backtracking in order to generate all the different positions a word could have in a 2D vector.

Let's say that I have a vector (which I prefer to use for memory reasons as I will be treating a lot of words) containing the word 'Hello'.

I generate a 2D vector of '.' characters 5x5 wide (so it can fit the word).

And then using a backtracking algorithm, I would like to generate all the positions this word could take with the letters still linked to each other.

For example :

. . . . .        . . . . .              . . . . .

H e . . .   or   . . . H .    or even   . . . . .

. l . . .        . . o e .              . . . . .

. l o . .        . . l l .              . . . . .

. . . . .        . . . . .              o l l e H

The algorithm I am interested in for 1D is (pseudo code):

function solve(word vector, size of vector)

 if end of word vector

    Print vector obtained