Could any coder/programer solve it? i'am really stucked

This is a very interesting problem. Did you come across this from some competitive programming site?

Also, before figuring out how many ways are there for them to cover the maximum number of cells, another interesting problem that we can try solving first is figuring out what this maximum number is.

I'm almost certain I've seen this problem somewhere before, where did you get it from? (And it seems you're not the only one asking for an answer... https://math.stackexchange.com/questions/2790244/counting-lattice-paths/2790300)

A simple but inefficient way to do this is to generate an algorithm (here pseudocode).

Here rooms is a set of all positions in the room (of course this can be replaced by a simple parameterisation), vis is the set of rooms already visitted, posD = the current position of Daniel an posE = current position of Esther.

Calling nextmoves(array of mxn positions,{},(0,0),(0,0)) will return an object containing the length of the longest possible explorations and the # of possible ways to achieve this.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

nextmoves(rooms,vis,posD,posE) {
    if posD==posE==End position, then:
        return {length=size(vis), count=1};
    else: 
    loop through all possibilities, i, for next posD and next posE in rooms
    so that posD(i) and posE(i) not in vis u {posD,posE}
    for each i set obj(i) := nextmoves(rooms,vis u {posD,posE},posD(i),posE(i)).
    set m := max all the obj(i).length.
    set c := sum of all obj(i).count for i with obj(i).length==m
    return {length=m, count=c};
}

In Python:

import itertools
def g(a):
    if len(a) == 2: return a[0]
    sum = 0
    for i in range(a[0]):
        sum += g([x-i for x in a[1:]])
    return sum

def lattice_ville(m, n):
    total = 0
    for i in itertools.combinations_with_replacement(range(1, m), r=n-2): #for each path Esther takes
        a = list(i)
        a.append(m-1)

        total += g(a) #add to the total the number of paths Daniel can take without intersecting
    return total

I'll work on a write-up for how I got here if anybody asks, but the solution is $\boxed{1176}$.

A good way to approach this problem is to look at it as a set of smaller problems. For this problem specifically, a good choice is:

How many ways can we traverse an $m\times n$ grid moving only north and east?

Imagine that we're programming a robot to move through some $m\times n$ grid. This robot only has two commands: move one space north, and move one space east. We know that the grid is $n$ spaces tall, so the robot has to move north $n-1$ times. We also know that the grid is $m$ spaces wide, so the robot has to move east $m-1$ times. So, in total, we have $(n-1)+(m-1)=n+m-2$ commands to give the robot, from which, we choose $n-1$ to tell it to move north. This means the robot can have ${m+n-2\choose n-1}$ possible paths. This is an application of the stars and bars method.

Before we continue, let's think about the maximum number of spaces Esther and Daniel can hit on a given board. We know that one path will visit $m+n-1$ spaces, and, in the maximal solution, two paths will only intersect at the beginning and end of the board, giving us $2(m+n-1)-2 = 2m+2n-4$ spaces. Note here that in a $1\times n$ or $m\times 1$ board, there is an exception, but we know that that will always have $1$ solution that will hit all $nm$ spaces, so that's not too worrying.

Let's think about the paths that Esther and Daniel can take. If they both move in the same direction on the first space, they will intersect, giving a non-optimal solution. We also know that they will not intersect at their second-to-last move. This means we know that one player must start moving east and end moving north, while the other must start moving north and end moving east.

This means that both players traverse their own, intersecting $m-1\times n-1$ sub-grid, with one sub-grid situated in the northwest corner of the board and the other situated in the southeast. That looks like this:

Where the red and blue lines represent each player's starting and ending moves, and the red and blue shading representing the grid they must traverse.

So now that we know this, how many ways can they both traverse these sub-grids?
To solve this, we must come up with a new way to represent the traversal of a grid. Let's label each point in the grid based on its distance from the leftmost square in the grid. That will look like this:

Then, any path can be described by a list of the labels of the grid squares where the player moves north. For example, the grid

can be described by the list [0, 2], since the player moves north in those squares.
It should be noted, though, that not every list corresponds with a valid lattice. The list [2, 1], for example, is not valid, since moving north first at label $2$ and then at label $1$ would require one step west, which is not allowed. To fix this, we add one restriction: The list must be non-decreasing. Two consecutive numbers can be the same, which corresponds to moving north twice in a row, but if there is a set of numbers in the list that decreases, we know the player must move west, so the grid is not allowed.

Very fortunately for us, there is a function in Python that generates non-decreasing lists of variable size from a given set of integers. This function is itertools.combinations_with_replacement. When used in a certain way, this returns an iterator that will give every non-decreasing list of size $n-1$ constructed from integers in the interval $[0, m]$. We construct this like so:

def lattice_ville(m, n):
    for i in itertools.combinations_with_replacement(range(1, m), r = n-2):
        # do something here
        pass

Note: From now on, we will assume Esther always travels east to start.

This will give us the list description of every solution to an $m-1 \times n-1$ rectangular grid. That's all well and good, but it surely isn't the solution. After all, one path for Esther could give way to a plethora of paths for Daniel. How do we solve this problem? Well, let's look at an example. Let's say we're on a $4\times 4$ grid and Esther traverses her $3\times 3$ sub-grid with the path represented by [1, 1]. That looks like this:

As you can see, Esther has blocked off a significant portion of Daniel's grid. We could use the same itertools.combinations_with_replacement for Daniel and just root out any intersecting paths that Daniel takes, but that would be wasteful and take a very long time to calculate. After all, just using itertools.combinations_with_replacement once puts our time complexity at $O({m+n-4 \choose n-2})$, which gets big fast, especially for square-like grids. We want a way to take the output of the itertools function and somehow discover how many paths Daniel can take. Let's call the weird lattice-based polygon that Daniel needs to traverse a lattice-gon. Then we have a new sub-problem.

How many ways can you traverse a lattice-gon?

Let's represent a lattice-gon in the same way we did a traversal path: as a list. For an $n$-tall lattice-gon, we can represent it as a list of integers, where the $i^{\text{th}}$ integer represents the length of the polygon at height $i$. Let's start with a $1$-tall lattice-gon. This is easy: there's only one way to traverse it! We just go east until we finish.

Let's try one level more: a $2$-tall lattice-gon. We know that list[0] will give us the length of the first row of the lattice-gon, so we have list[0] places to go north. Once we go north, though, the rest of the problem is analogous to solving a $1$-tall lattice-gon, so we know that the number of solutions is equal to list[0].

The next one is harder: a $3$-tall lattice-gon. list[0] will give us the length of the first row of the lattice-gon. So we have list[0] ways to do this. Let's say we go north as soon as we can. Then, number of solutions branching from that path is analogous to the number of solutions to the lattice-gon list[1:], which is the list without its first element. If we go east $x$ times before we go north, we will have cut off the first $x$ elements of each row, so the number of solutions branching from that path is analogous to the number of solutions to the lattice-gon [i-x for i in list[1:]]. The total number of solutions is the sum of the number of solutions for each branching path.

This recursive pattern repeats for everything greater than $3$.

One more thing before we write this in Python, though: It actually doesn't matter how long the top row is, so we will omit it in our list. So the function looks like this:

def lattice_gon(a):
    if len(a) == 0: return 1
    if len(a) == 1: return a[0]
    sum = 0
    for i in range(a[0]):
        sum += lattice_gon([x-i for x in a[1:]])
    return sum

So we have two functions, but how do we connect them together? Well, it's really simple: The way that we used the itertools function meshes perfectly with our lattice_gon function! I'll leave it as an exercise to the reader to figure out why, but it shouldn't be too hard.

So our total function looks like:

import itertools
def lattice_gon(a):
    if len(a) == 0: return 1
    if len(a) == 1: return a[0]
    sum = 0
    for i in range(a[0]):
        sum += lattice_gon([x-i for x in a[1:]])
    return sum

def lattice_ville(m, n):
    if m < 3 or n < 3: return 1

    total = 0
    for i in itertools.combinations_with_replacement(range(1, m), r=n-2): #for each path Esther takes
        total += lattice_gon(i) #add to the total the number of paths Daniel can take without intersecting
    return total

print(lattice_ville(5, 7))

This is a really slow function, but is slightly faster than brute-force as it generates no wrong solutions. I think it runs in $O(m^2{m+n-4 \choose n-2}) \in O(m^2(m+n)!)$

Which is much faster than the brute force solution, which runs in $O(((m+n)!)^2)$

lattice_ville(5,7) returns $\boxed{1176}$.