#include <list>
#include <cmath>
#include <string>
#include <iostream>
#include <cassert>
#include <cstdlib>
#include <algorithm>

const int X_MAX = 6;
const int Y_MAX = 6;

class point {
public:
	int x;
	int y;
	int distance;

	point() : x(0), y(0) {
	}

	point(int x, int y) : x(x), y(y), distance(0) {
	}

	point(int x, int y, int d) : x(x), y(y), distance(d) {
	}

	~point() {
	}

	void print() const {
		std::cout << "(" << x << "," << y << ")" << std::endl;
	}

	bool operator==(point p) const {
		return x == p.x && y == p.y;
	}

	bool is_neighbour(point p) {
		return ((std::abs((double) x - p.x) == 1 && y == p.y) ||
				(std::abs((double) y - p.y) == 1 && x == p.x));
	}

	point west() {
		assert((y - 1) > 0);
		return point(x, y - 1, distance+1);
	}

	point east() {
		assert(y + 1 < Y_MAX);
		return point(x, y + 1, distance+1);
	}

	point north() {
		assert(x - 1 > 0);
		return point(x - 1, y, distance+1);
	}

	point south() {
		assert(x + 1 < X_MAX);
		return point(x + 1, y, distance+1);
	}
};


static std::list<point> visited;
static int length;

bool is_point_visited(point p) {
	std::list<point>::iterator result = std::find(visited.begin(), visited.end(), p);
	return *result == p;
}

// Adjust coordinates to have (0,0) at the bottom left-hand corner.

char get_char(point p, std::string* map) {
	return map[Y_MAX - p.y - 1][p.x];
}

// Will be useful for the terminating condition.

bool has_arrived(point current, point end) {
	return current.is_neighbour(end);
}

std::list<point> find_candidates(point current, std::string* map) {
	std::list<point> candidates;

	// West
	if (current.y - 1 > 0 && get_char(current.west(), map) == '0') {
		if (!is_point_visited(current.west()))
			candidates.push_back(current.west());
	}

	// East
	if (current.y + 1 < Y_MAX && get_char(current.east(), map) == '0') {
		if (!is_point_visited(current.east()))
			candidates.push_back(current.east());
	}

	// North
	if (current.x - 1 > 0 && get_char(current.north(), map) == '0') {
		if (!is_point_visited(current.north()))
			candidates.push_back(current.north());
	}

	// South
	if (current.x + 1 < X_MAX && get_char(current.south(), map) == '0') {
		if (!is_point_visited(current.south()))
			candidates.push_back(current.south());
	}

	return candidates;
}

bool iter(point current, point end, std::string* map) {
	visited.push_front(current);
	if (has_arrived(current, end)) {
		length = current.distance;
		return true;
	}
	std::list<point> candidates = find_candidates(current, map);
	if (candidates.empty()) {
		return false;
	} else {
		while (!candidates.empty()) {
			if (iter(candidates.front(), end, map)) {
				return true;
			} else {
				candidates.pop_front();
			}
		}
		return false;
	}
}

int main() {

	std::string map[] = {"1000020",
						 "0100113",
						 "3003000",
						 "2033000",
						 "2003111",
						 "2000010"};

	point start(0, 0);
	point end(5, 5);

	length = -1;

	if (iter(start, end, map)) {
		std::cout << "indeed" << std::endl;
		std::cout << "bridge is " << length << " long." << std::endl;
	} else {
		std::cout << "nope" << std::endl;
	}
	std::cout << "visited " << visited.size() << " nodes." << std::endl;
}