Графы для самых маленьких: DFS

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <cstdio>
#include <map>
#include <string>
#include <iostream>

using namespace std;

struct edge
{
	int v, c, f, r;

	edge(int _v, int _c, int _r) : v(_v), c(_c), f(0), r(_r)
	{};
};

const int INF = 3;

vector<vector<edge> > edges;
vector<int> mark;
vector<pair<int, int> > p;
int TIME;

stack<int> dfs_stack;

bool DFS(int v, int t)
{
	dfs_stack.push(v);
	while (!dfs_stack.empty() && v != t)
	{
		v = dfs_stack.top();
		dfs_stack.pop();
		for (int i = 0; i < (int)edges[v].size(); ++i)
		{
			if (mark[edges[v][i].v] == TIME || edges[v][i].f == edges[v][i].c)
			{
				continue;
			}
			mark[edges[v][i].v] = TIME;
			p[edges[v][i].v] = make_pair(v, i);
			dfs_stack.push(edges[v][i].v);
		}
	}
	while (!dfs_stack.empty())
	{
		dfs_stack.pop();
	}
	return v == t;
}

bool DFS2(int v, int t)
{
	dfs_stack.push(v);
	while (!dfs_stack.empty() && v != t)
	{
		v = dfs_stack.top();
		dfs_stack.pop();
		for (int i = 0; i < (int)edges[v].size(); ++i)
		{
			if (mark[edges[v][i].v] == TIME || edges[v][i].f <= 0)
			{
				continue;
			}
			mark[edges[v][i].v] = TIME;
			p[edges[v][i].v] = make_pair(v, i);
			dfs_stack.push(edges[v][i].v);
		}
	}
	while (!dfs_stack.empty())
	{
		dfs_stack.pop();
	}
	return v == t;
}

int flow(int s, int d)
{
	TIME = 1;
	mark.assign(edges.size(), 0);
	p.assign(edges.size(), make_pair(0, 0));
	int ans = 0;
	for (; DFS(s, d); ++TIME)
	{
		++ans;
		for (int v = d; v != s; v = p[v].first)
		{
			++edges[p[v].first][p[v].second].f;
			--edges[v][edges[p[v].first][p[v].second].r].f;
		}
	}
	return ans;
}

vector<vector<int> > decompose(int s, int d)
{
	vector<vector<int> > ans;
	for (++TIME; DFS2(s, d); ++TIME)
	{
		vector<int> path;
		for (int v = d; v != s; v = p[v].first)
		{
			path.push_back(v);
			--edges[p[v].first][p[v].second].f;
			++edges[v][edges[p[v].first][p[v].second].r].f;
		}
		path.push_back(s);
		reverse(path.begin(), path.end());
		ans.push_back(path);
	}
	return ans;
}

void add_edge(vector<vector<edge> > &edges, int s, int d, int c)
{
	edges[s].push_back(edge(d, c, (int)edges[d].size()));
	edges[d].push_back(edge(s, 0, (int)edges[s].size() - 1));
}

void add_vertex_restrictions(int r)
{
	int n = (int)edges.size();
	vector<vector<edge> > new_edges(n * 2);
	for (int i = 0; i < n; ++i)
	{
		add_edge(new_edges, i * 2, i * 2 + 1, r);
	}
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < (int)edges[i].size(); ++j)
		{
			add_edge(new_edges, 2 * i + 1, 2 * edges[i][j].v, edges[i][j].c);
		}
	}
	edges = new_edges;
}

void solve(vector<string> world)
{
	pair<int, int> start = make_pair(-1, -1);
	pair<int, int> finish = make_pair(-1, -1);
	pair<int, int> middle = make_pair(-1, -1);
	int n = (int)world.size();
	int m = (int)world[0].size();
	for (int i = 0; i < n; ++i)
	{
		if ((int)world[i].size() != m)
		{
			cout << "Different lengths of lines!\n";
			return;
		}
		for (int j = 0; j < m; ++j)
		{
			if (world[i][j] == 'S')
			{
				if (start.first == -1)
				{
					start = make_pair(i, j);
				}
				else
				{
					cout << "Two cells marked as start!\n";
					return;
				}
			}
			if (world[i][j] == 'F')
			{
				if (finish.first == -1)
				{
					finish = make_pair(i, j);
				}
				else
				{
					cout << "Two cells marked as finish!\n";
					return;
				}
			}
			if (world[i][j] == '*')
			{
				if (middle.first == -1)
				{
					middle = make_pair(i, j);
				}
				else
				{
					cout << "Two cells marked as middle!\n";
					return;
				}
			}
		}
	}
	if (start.first < 0)
	{
		cout << "No cells marked as start!\n";
		return;
	}
	if (finish.first < 0)
	{
		cout << "No cells marked as finish!\n";
		return;
	}
	if (middle.first < 0)
	{
		cout << "No cells marked as middle!\n";
		return;
	}
	edges.assign(n * m + 1, vector<edge>());
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			if (world[i][j] == '#')
			{
				continue;
			}
			if (world[i][j] == 'F' || world[i][j] == 'S')
			{
				add_edge(edges, i * m + j, n * m, INF);
			}
			if (i > 0 && world[i - 1][j] != '#')
			{
				add_edge(edges, i * m + j, (i - 1) * m + j, INF);
			}
			if (i < n - 1 && world[i + 1][j] != '#')
			{
				add_edge(edges, i * m + j, (i + 1) * m + j, INF);
			}
			if (j > 0 && world[i][j - 1] != '#')
			{
				add_edge(edges, i * m + j, i * m + j - 1, INF);
			}
			if (j < m - 1 && world[i][j + 1] != '#')
			{
				add_edge(edges, i * m + j, i * m + j + 1, INF);
			}
		}
	}
	add_vertex_restrictions(1);
	int f = flow((middle.first * m + middle.second) * 2 + 1, n * m * 2);
	if (f < 2)
	{
		cout << "No paths found :\'(\n";
		return;
	}
	vector<vector<int> > paths = decompose((middle.first * m + middle.second) * 2 + 1, n * m * 2);
	vector<vector<int> > compressed_paths(paths.size());
	for (int i = 0; i < (int)paths.size(); ++i)
	{
		for (int j = 0; j < (int)paths[i].size(); ++j)
		{
			if (paths[i][j] % 2 == 1)
			{
				compressed_paths[i].push_back(paths[i][j] / 2);
			}
		}
	}
	if (compressed_paths[0].back() != start.first * m + start.second)
	{
		swap(compressed_paths[0], compressed_paths[1]);
	}
	reverse(compressed_paths[0].begin(), compressed_paths[0].end());
	for (int i = 0; i < compressed_paths[0].size() - 1; ++i)
	{
		cout << "(" << compressed_paths[0][i] / m << ", " << compressed_paths[0][i] % m << ")\n";
	}
	for (int i = 0; i < compressed_paths[1].size(); ++i)
	{
		cout << "(" << compressed_paths[1][i] / m << ", " << compressed_paths[1][i] % m << ")\n";
	}
}

int main(void)
{
	vector<string> world;
	string s;
	while (true)
	{
		getline(cin, s);
		if (s == "")
		{
			break;
		}
		world.push_back(s);
	}
	solve(world);
	getline(cin, s);
	return 0;
}