Cod sursa(job #1141705)

Utilizator BionicMushroomFMI - Dumitrescu Tiberiu Alexandru BionicMushroom Data 13 martie 2014 02:20:22
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.57 kb
#include<fstream>
#include<queue>
using namespace std;

struct position { short row, col, step; };

void read_init(short** &R, short ** &J, short &max_row, short &max_col, position &r_start, position &j_start)
{
	ifstream file("rj.in");
	char c;
	file >> max_row >> max_col;
	R = new short*[max_row];
	J = new short*[max_row];
	for (int i = 0; i < max_row; i++)
	{
		R[i] = new short[max_col];
		J[i] = new short[max_col];
		for (int j = 0; j < max_col; j++)
		{
			do
			{
				c = file.get();
			} while (c == '\n');
			if (c == 'X')
				R[i][j] = J[i][j] = -1;
			else
				if (c == ' ')
					R[i][j] = J[i][j] = 0;
				else
					if (c == 'R')
					{
						R[i][j] = J[i][j] = -1;
						r_start.row = i;
						r_start.col = j;
						r_start.step = 1;
					}
					else
						if (c == 'J')
						{
							R[i][j] = J[i][j] = -1;
							j_start.row = i;
							j_start.col = j;
							j_start.step = 1;
						}
		}
	}
	file.close();
}

void meeting_point(short **R, short **J, short max_row, short max_col, position r_pos, position j_pos)
{
	ofstream g("rj.out");
	bool found = false;
	queue<position> r_q, j_q;
	r_q.push(r_pos);
	j_q.push(j_pos);
	while (!found)
	{
		do
		{
			r_pos = r_q.front();
			r_q.pop();
			if (r_pos.row - 1 >= 0)
			{
				if (r_pos.col - 1 >= 0 && !R[r_pos.row - 1][r_pos.col - 1])
				{
					R[r_pos.row - 1][r_pos.col - 1] = r_pos.step + 1;
					r_q.push({ r_pos.row - 1, r_pos.col - 1, r_pos.step + 1 });
				}
				if (!R[r_pos.row - 1][r_pos.col])
				{
					R[r_pos.row - 1][r_pos.col] = r_pos.step + 1;
					r_q.push({ r_pos.row - 1, r_pos.col, r_pos.step + 1 });
				}
				if (r_pos.col + 1 < max_col && !R[r_pos.row - 1][r_pos.col + 1])
				{
					R[r_pos.row - 1][r_pos.col + 1] = r_pos.step + 1;
					r_q.push({ r_pos.row - 1, r_pos.col + 1, r_pos.step + 1 });
				}
			}
			if (r_pos.col - 1 >= 0 && !R[r_pos.row][r_pos.col - 1])
			{
				R[r_pos.row][r_pos.col - 1] = r_pos.step + 1;
				r_q.push({ r_pos.row, r_pos.col - 1, r_pos.step + 1 });
			}
			if (r_pos.col + 1 < max_col && !R[r_pos.row][r_pos.col + 1])
			{
				R[r_pos.row][r_pos.col + 1] = r_pos.step + 1;
				r_q.push({ r_pos.row, r_pos.col + 1, r_pos.step + 1 });
			}
			if (r_pos.row + 1 < max_row)
			{
				if (r_pos.col - 1 >= 0 && !R[r_pos.row + 1][r_pos.col - 1])
				{
					R[r_pos.row + 1][r_pos.col - 1] = r_pos.step + 1;
					r_q.push({ r_pos.row + 1, r_pos.col - 1, r_pos.step + 1 });
				}
				if (!R[r_pos.row + 1][r_pos.col])
				{
					R[r_pos.row + 1][r_pos.col] = r_pos.step + 1;
					r_q.push({ r_pos.row + 1, r_pos.col, r_pos.step + 1 });
				}
				if (r_pos.col + 1 < max_col && !R[r_pos.row + 1][r_pos.col + 1])
				{
					R[r_pos.row + 1][r_pos.col + 1] = r_pos.step + 1;
					r_q.push({ r_pos.row + 1, r_pos.col + 1, r_pos.step + 1 });
				}
			}
		} while (!r_q.empty() && r_q.front().step == r_pos.step);
		do
		{
			j_pos = j_q.front();
			j_q.pop();
			if (j_pos.row - 1 >= 0)
			{
				if (j_pos.col - 1 >= 0 && !J[j_pos.row - 1][j_pos.col - 1])
				{
					J[j_pos.row - 1][j_pos.col - 1] = j_pos.step + 1;
					if (J[j_pos.row - 1][j_pos.col - 1] == R[j_pos.row - 1][j_pos.col - 1])
					{
						found = true;
						g << j_pos.step + 1 << ' ' << j_pos.row << ' ' << j_pos.col;
						break;
					}
					j_q.push({ j_pos.row - 1, j_pos.col - 1, j_pos.step + 1 });
				}
				if (!J[j_pos.row - 1][j_pos.col])
				{
					J[j_pos.row - 1][j_pos.col] = j_pos.step + 1;
					if (J[j_pos.row - 1][j_pos.col] == R[j_pos.row - 1][j_pos.col])
					{
						found = true;
						g << j_pos.step + 1 << ' ' << j_pos.row << ' ' << j_pos.col + 1;
						break;
					}
					j_q.push({ j_pos.row - 1, j_pos.col, j_pos.step + 1 });
				}
				if (j_pos.col + 1 < max_col && !J[j_pos.row - 1][j_pos.col + 1])
				{
					J[j_pos.row - 1][j_pos.col + 1] = j_pos.step + 1;
					if (J[j_pos.row - 1][j_pos.col + 1] == R[j_pos.row - 1][j_pos.col + 1])
					{
						found = true;
						g << j_pos.step + 1 << ' ' << j_pos.row << ' ' << j_pos.col + 2;
						break;
					}
					j_q.push({ j_pos.row - 1, j_pos.col + 1, j_pos.step + 1 });
				}
			}
			if (j_pos.col - 1 >= 0 && !J[j_pos.row][j_pos.col - 1])
			{
				J[j_pos.row][j_pos.col - 1] = j_pos.step + 1;
				if (J[j_pos.row][j_pos.col - 1] == R[j_pos.row][j_pos.col - 1])
				{
					found = true;
					g << j_pos.step + 1 << ' ' << j_pos.row + 1 << ' ' << j_pos.col;
					break;
				}
				j_q.push({ j_pos.row, j_pos.col - 1, j_pos.step + 1 });
			}
			if (j_pos.col + 1 < max_col && !J[j_pos.row][j_pos.col + 1])
			{
				J[j_pos.row][j_pos.col + 1] = j_pos.step + 1;
				if (J[j_pos.row][j_pos.col + 1] == R[j_pos.row][j_pos.col + 1])
				{
					found = true;
					g << j_pos.step + 1 << ' ' << j_pos.row + 1 << ' ' << j_pos.col + 2;
					break;
				}
				j_q.push({ j_pos.row, j_pos.col + 1, j_pos.step + 1 });
			}
			if (j_pos.row + 1 < max_row)
			{
				if (j_pos.col - 1 >= 0 && !J[j_pos.row + 1][j_pos.col - 1])
				{
					J[j_pos.row + 1][j_pos.col - 1] = j_pos.step + 1;
					if (J[j_pos.row + 1][j_pos.col - 1] == R[j_pos.row + 1][j_pos.col - 1])
					{
						found = true;
						g << j_pos.step + 1 << ' ' << j_pos.row + 2 << ' ' << j_pos.col;
						break;
					}
					j_q.push({ j_pos.row + 1, j_pos.col - 1, j_pos.step + 1 });
				}
				if (!J[j_pos.row + 1][j_pos.col])
				{
					J[j_pos.row + 1][j_pos.col] = j_pos.step + 1;
					if (J[j_pos.row + 1][j_pos.col] == R[j_pos.row + 1][j_pos.col])
					{
						found = true;
						g << j_pos.step + 1 << ' ' << j_pos.row + 2 << ' ' << j_pos.col + 1;
						break;
					}
					j_q.push({ j_pos.row + 1, j_pos.col, j_pos.step + 1 });
				}
				if (j_pos.col + 1 < max_col && !J[j_pos.row + 1][j_pos.col + 1])
				{
					J[j_pos.row + 1][j_pos.col + 1] = j_pos.step + 1;
					if (J[j_pos.row + 1][j_pos.col + 1] == R[j_pos.row + 1][j_pos.col + 1])
					{
						found = true;
						g << j_pos.step + 1 << ' ' << j_pos.row + 2 << ' ' << j_pos.col + 2;
						break;
					}
					j_q.push({ j_pos.row + 1, j_pos.col + 1, j_pos.step + 1 });
				}
			}
		} while (!j_q.empty() && j_q.front().step == j_pos.step);
	}
	g.close();
}

void clean(short** &R, short ** &J, short &max_row, short &max_col)
{
	for (int i = 0; i < max_row; i++)
	{
		delete[] R[i];
		delete[] J[i];
	}
	delete[] R;
	delete[] J;
	R = NULL;
	J = NULL;
	max_row = max_col = 0;
}

int main()
{
	short **R, **J, max_row, max_col;
	position r_start, j_start;
	read_init(R, J, max_row, max_col, r_start, j_start);
	meeting_point(R, J, max_row, max_col, r_start, j_start);
	clean(R, J, max_row, max_col);
	return 0;
}