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();
}