Analysis: What's Up With Gravity? by Fatih Gelgi

This is obviously a shortest path problem. We can solve the problem using Dijkstra's shortest path algorithm with a small twist. In this case, nodes are the cells in the grid. There is an edge between two nodes (a,b) if b can be reached by left, right moves or flipping the gravity from a. Notice that it is only necessary to keep the "stable cells" as nodes - the cells that CB doesn't fall down in one of the gravity directions. Since there can be at most O(N^2) edges, running time is O(N^2 log N^2) using a priority queue.

Since the problem is a shortest path problem and the edges can be 0 or 1 distance, we can also solve the problem modifying BFS. Remember that the distance of a node has to be always smaller than another node which is added later in a BFS queue. Hence, we have to add the queue all reachable nodes (via left and right moves) in the same flip. To find all reachable nodes from a node, we can use either DFS or BFS. Since each cell is visited only O(1) time, the total running time is O(N^2) which is slightly faster than the former solution.

A sample solution with Dijkstra is as follows:

```#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

#define MAX 502

int n,m,mark[MAX][MAX];
string mat[MAX];

struct Point
{	int y,x; };

// comparison criteria for priority queue
bool operator<(Point a,Point b)
{
// smaller number of flips first
return mark[a.y][a.x]>mark[b.y][b.x];
}

priority_queue<Point> q;

// falling down in the given direction dir={-1:up,1:down}
Point fall(Point p,int dir)
{
for (; ; p.y+=dir)
{
if (mat[p.y][p.x]=='D') break;
if (p.y+dir<0 || p.y+dir>=n) return {-1,-1};
if (mat[p.y+dir][p.x]=='#') break;
}
return p;
}

// make move k={-1:left,0:flip,1:right}
//	in the given direction dir={-1:up,1:down}
Point action(Point p,int k,int dir)
{
// move left or right
if (k)
{
p.x+=k;
if (p.x<0 || p.x>=m || mat[p.y][p.x]=='#') return {-1,-1};
}
// flip
else dir=-dir;
return fall(p,dir);
}

int main()
{
ifstream fin("gravity.in");
fin >> n >> m;
for (int i=0; i<n; i++)
fin >> mat[i];
fin.close();

Point c,d;
for (int i=0; i<n; i++)
for (int j=0; j<m; j++)
if (mat[i][j]=='C') c=fall({i,j},1);
else if (mat[i][j]=='D') d={i,j};

if (c.y>=0)
{
q.push(c);
mark[c.y][c.x]=1;
for ( ; !q.empty(); )
{
Point e=q.top();
q.pop();
if (e.y==d.y && e.x==d.x) break;

// add legal moves to the priority queue
for (int i=-1,dir=mark[e.y][e.x]%2 ? 1 : -1; i<=1; i++)
{
Point p=action(e,i,dir);
if (p.y!=-1 && !mark[p.y][p.x])		// add if not visited before
{
mark[p.y][p.x]=mark[e.y][e.x];
if (!i) mark[p.y][p.x]++;	// if the move is a flip
q.push(p);
}
}
}
}

ofstream fout("gravity.out");
fout << mark[d.y][d.x]-1 << endl;
fout.close();
}
```

BFS implementation sample is below:

```#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

#define MAX 502
#define DIR(e) (mark[e.y][e.x]%2 ? 1 : -1)

int n,m,mark[MAX][MAX];
string mat[MAX];

struct Point
{	int y,x; } c,d;

queue<Point> q;

// falling down in the given direction dir={-1:up,1:dowm}
Point fall(Point p,int dir)
{
for (; ; p.y+=dir)
{
if (mat[p.y][p.x]=='D') break;
if (p.y+dir<0 || p.y+dir>=n) return {-1,-1};
if (mat[p.y+dir][p.x]=='#') break;
}
return p;
}

// make move k={-1:left,0:flip,1:right}
//	in the given direction dir={-1:up,1:down}
Point action(Point p,int k,int dir)
{
// move left or right
if (k)
{
p.x+=k;
if (p.x<0 || p.x>=m || mat[p.y][p.x]=='#') return {-1,-1};
}
// flip
else dir=-dir;
return fall(p,dir);
}

// try all points that has same flip using DFS
int dfs(Point p,int flip)
{
if (p.y==-1 || mark[p.y][p.x]) return 0;
mark[p.y][p.x]=flip;
if (p.y==d.y && p.x==d.x) return 1;
q.push(p);
int dir=DIR(p);
return dfs(action(p,-1,dir),flip) || dfs(action(p,1,dir),flip);
}

int main()
{
ifstream fin("gravity.in");
fin >> n >> m;
for (int i=0; i<n; i++)
fin >> mat[i];
fin.close();

for (int i=0; i<n; i++)
for (int j=0; j<m; j++)
if (mat[i][j]=='C') c=fall({i,j},1);
else if (mat[i][j]=='D') d={i,j};

// BFS
if (!dfs(c,1))
for (; !q.empty(); )
{
Point e=q.front();
q.pop();
Point p=action(e,0,DIR(e));		// flip the gravity
// push all the points that has the same flip
if (dfs(p,mark[e.y][e.x]+1)) break;
}

ofstream fout("gravity.out");
fout << mark[d.y][d.x]-1 << endl;
fout.close();
}
```
Author's Note: This problem is inspired from the game VVVVVV. The problem was initially called BBBBBB but it was decided that was too confusing.