module app;

import core.bitop;

import std.algorithm;
import std.array;
import std.bigint;
import std.container.rbtree;
import std.conv;
import std.stdio;
import std.string;
import std.traits;

struct Input
{
	int h, w;
	int ch, cw;
	int dh, dw;
	string[] s;
}

void parseInput(T)(out Input input, T adapter)
{
	with (input)
	{
		adapter.readf!"%d %d\n"(h, w);
		adapter.readf!"%d %d\n"(ch, cw);
		adapter.readf!"%d %d\n"(dh, dw);
		s.length = h;
		foreach (i; 0..h)
		{
			s[i] = adapter.readln();
		}
	}
}

struct Output
{
}

auto main2(Input* input)
{
	struct Field
	{
		int step = 0;
		bool searched = false;
	}

	Field[][] fieldMap;

	fieldMap.length = input.h;
	foreach (irow, ref row; fieldMap)
	{
		row.length = input.w;
		foreach (x, field; input.s[irow])
		{
			if (field == '#')
			{
				row[x].step = int.min; // 壁
				row[x].searched = true;
			}
			else
			{
				row[x].step = int.max; // 未確認
				row[x].searched = false;
			}
		}
	}

	ulong searchedFields = 0;

	void fill(int y, int x, int count)
	{
		if (fieldMap[y][x].searched)
			return;

		int prev = fieldMap[y][x].step;

		if (prev < count)
			return;

		fieldMap[y][x].step = count;
		fieldMap[y][x].searched = true;

		searchedFields++;

		foreach (h; max(y - 2, 0)..min(y + 3, input.h))
		{
			foreach (w; max(x - 2, 0)..min(x + 3, input.w))
			{
				if (fieldMap[h][w].step == int.max)
					fieldMap[h][w].step = count + 1;
			}
		}

		if (y != 0)
			fill(y - 1, x, count);
		if (x != input.w - 1)
			fill(y, x + 1, count);
		if (y != input.h - 1)
			fill(y + 1, x, count);
		if (x != 0)
			fill(y, x - 1, count);
	}

	fill(input.ch - 1, input.cw - 1, 0);

	while (true)
	{
		if (fieldMap[input.dh - 1][input.dw - 1].searched)
			return fieldMap[input.dh - 1][input.dw - 1].step;

		auto oldSearchedFields = searchedFields;

		foreach (y, row; fieldMap)
		{
			foreach (x, field; row)
			{
				if (!field.searched && field.step != int.max)
				{
					fill(cast(int)y, cast(int)x, field.step);
				}
			}
		}

		if (oldSearchedFields == searchedFields)
			return -1;
	}

}

alias retType = ReturnType!main2;
static if (!is(retType == void))
{
	unittest { writeln("begin unittest"); }
	auto _placeholder_ = ReturnType!main2.init;

	unittest // example1
	{
		string example =
`4 4
1 1
4 4
..#.
..#.
.#..
.#..`;
		if (example.empty) return;
		Input input = void;
		parseExample(input, example);
		auto result = main2(&input);
		printResult(result);
		assert(result == 1);
	}

	unittest // example2
	{
		string example =
`4 4
1 4
4 1
.##.
####
####
.##.`;
		if (example.empty) return;
		Input input = void;
		parseExample(input, example);
		auto result = main2(&input);
		printResult(result);
		assert(result == -1);
	}

	unittest // example3
	{
		string example =
`4 4
2 2
3 3
....
....
....
....`;
		if (example.empty) return;
		Input input = void;
		parseExample(input, example);
		auto result = main2(&input);
		printResult(result);
		assert(result == 0);
	}

	unittest { writeln("end unittest"); }

	void parseExample(out Input input, string example)
	{
		parseInput(input, new StringAdapter(example));
	}
}

class StdinAdapter
{
	// readf!"%s"は使えない
	// https://issues.dlang.org/show_bug.cgi?id=19820
	uint readf(alias format, A...)(auto ref A args) { return std.stdio.readf!format(args); }
	string readln() { return std.stdio.readln().strip(); }
}

class StringAdapter
{
	import std.format;
	string _s;
	this(string input) { _s = input; }
	uint readf(alias format, A...)(auto ref A args) { return _s.formattedRead!format(args); }
	string readln()
	{
		auto i = _s.countUntil("\n");
		if (i == -1) i = _s.length;
		string ret = _s[0..i];

		if (i == _s.length)
			_s = _s[i..$];
		else
			_s = _s[i+1..$];
		return ret;
	}
}

void printResult(T)(T result)
{
	static if (isFloatingPoint!T) writefln("%f", result);
	else writeln(result);
}

void main()
{
	Input input = void;
	parseInput(input, new StdinAdapter());
	static if (is(retType == void))
		main2(&input);
	else
	{
		auto result = main2(&input);
		printResult(result);
	}
}
