CareerCup

Here I suppose that we can only move left-right-bottom-up and not diagonally.

Such path exists if either M is even, or N is even. Suppose M is even. Then path is simple - begin from (0, 0), go down, then ascend in a snake-like manner, filling all cells. Since there are even number of rows, on the M-1 row we will go to the right, on M-2 to the left, ..., and on 0 - to the left back to (0, 0), since M - 2 is even.

Now - proof that if both coordinates are odd, there exists no such path.
Color all cells in a chess board manner. Since there are N*M cells, which is odd, it means that path from first cell to last cell through all cells will contain N*M - 1 moves, which is even. Each move changes color of current cell from black to white or vice versa. This means that first and last cells will be of the same color - this means that we will never be able to move from the last cell to the first in order to turn hamiltonian path into a cycle.

The Start cell can be anywhere or is always located at 0,0; Can you clarify next cell to the start node I mean is right and left or could be any of the 8 cells surrounding it ?

The answer would depend on whether or not one allows diagonal segments, such as a segment (0,0) -> (1,1) If you do not allow this parity arguments come into play.

Previous comments are not entirely correct

- Assuming that the start & end node are adjacent to each other, not diagonal, and you can only move side to side, not diagonal, there is a solution if M is even or N is even, as LONG AS THE CELLS ARE CONTIGUOUS

IF M=2 or N=2 then you can have a scenario where the start & end cells split the space into 2 sides that are unreachable from each other


- If the start & end node are diagonal, then this is solveable as long as M is odd & N is odds, and you don't isolate one of the nodes in an unreachable corner

Pollllklkk,m. Jjj. B. M n. Mbbbbgyghnmk,l..l mm. ...

I think that next to start node doesn't mean to be diagonal

Should be pretty easy. And need to start from bottom left corner of the matrix

int main()
{
   int matrix[4][4]={ {0, 0, 0, 0},
                      {0, 0, 0, 0},
                      {0, 1, 1, 1},
                      {0, 1, 1, 1},
                };
   int row = 3 ; 
   int col = 0;
   int zero = 0;
   
   while( col < 4 )
   {
        if( matrix[row][col] == 0 )
        {
            zero += ( row + 1 );
            col++;
        }
        else
        {
            row--;
        }
   }

    printf("Zero:%d\n", zero);

}

Is this not travelling salesman problem ?

//this appears some kind of brain teaser, you can draw such a path for any M>1 and N>1
static boolean checkSpanningPath(int M,int N)
{
	return M>1 && N>1;
}