Techniques to solve Problem LightOJ 1057 - Collecting Gold

LightOJ 1057 - Collecting Gold 

Category: This problem is a dynamic programming problem. Particularly this problem can be solved by bitmask dynamic programming technique.This problem can also be solved by using breath first search.

Techniques: When I have solved this problem then I was tried it by recursive dynamic programming technique. Your sample test cases may pass by these techniques but in case of mine I have defeat my code by a critical test case of mine. Then I thought it from different angle and I have solved it by the technique of bit-mask dynamic programming. 
It is little hard to model the problem in bitmasking. If you don't have any idea about bit-masking then please learn it from internet. There are available resources. I did the same. 

In the problem it has been told that the problem could have at best 15 gold. When the input size of a DP problem is less than 16 then this problem could be a bit-mask DP. 

The gold has 15 pieces and a initial location(x) together makes 16. I think now you have got the clue. 

At first please keep the locations of all gold pieces in a separate array of two dimension by index starting from 1. Now, use the zero index to store the location of initial position.
Now, calculate the distance of every gold pieces to each other including the initial position.
Suppose, Array to store locations is 'a' and array to store the distances is 'b'. My code was:
      repc(i,0,m-1)
      repc(j,0,n-1)
      {
          if(s[i][j]=='x'){ a[0][1]=i;a[0][2]=j;}
          else if(s[i][j]=='g') {a[++c][1]=i;a[c][2]=j;}
      }
      repc(i,0,c)
      repc(j,i+1,c)
      {
        b[i][j]=b[j][i]=max(abs(a[i][1]-a[j][1]),abs(a[i][2]-a[j]  [2]));
      }
I am not describing the code. You can try if you are willing to do so. The following part is interesting in code: "max(abs(a[i][1]-a[j][1]),abs(a[i][2]-a[j][2]))" 
Isn't it?
This is the distance from one coordinate to another coordinate if you can move in all 8 direction. For four direction this equation could be failed!! 
Please put two coordinates in your paper and try to figure out what's going on in this equation.

Now, everything is ready. You can start bit-masking procedure recursively. The memory you can use is at best 16*2^16. 
If you have learn the bit-mask DP technique already then it shouldn't be a problem for you at all. If you don't then comment for further help. I shall try in shaa Allah.
Test Cases:
Input:
3
3 4
x..g
...g
g.gg

3 4
x..g
...g
gggg

20 20
....................
....................
.g...g..............
.............g......
....................
....g...............
..........g.........
g...................
.........x....g.....
....................
....................
...g................
....................
.....g......g.......
....................
..g.................
...........g...g....
....................
....................
g..................g

Output:
10
10
71