I thought about this problem for a while, and someone proved me that this is NP hard, cause its 'find hamiltonian path' if theres only 1 color. I might be wrong tho, but i didnt came up with any flow-like solution, except for 'shuffle-shuffle-shuffle till we good', but it has exponentional complexity

max-cost(take negative costs) max-flow solution: choose which one of cells you start with and which you end with in one of 2^X ways for each color. Now (start,end) of each color is fixed. Edges from super-source to starts with cap=1, cost=0, from ends to super-sink with cap=1, cost=0, from each vertex to adjacent vertices(cap=1,cost=0). Also, vertex capacities=1(cap=1,cost=1). If flow=X and cost=n*m-2*X, then output solution backtracking from residual edges.
Time Complexity: O(2^X*F(n*m)) where F(n*m) denotes flow complexity(depends on flow algorithm used) for a single graph.