#include <stdio.h>
#include <ctype.h>

#define WIDTH 41
#define HEIGHT 57

struct Node;

struct Edge
{
	void init(bool n_out) { out = n_out; to = 0; len = 0; from = 0; pass = false; }
	bool out;
	Node* to;
	int len;
	Node* from;
	bool pass;
};

#define RIGHT (1<<0)
#define DOWN  (1<<1)
#define LEFT  (1<<2)
#define UP    (1<<3)

int arrows(char c)
{
	switch (c)
	{
		case '.' : return 0;
		case 'r' : return RIGHT;
		case 'd' : return DOWN;
		case 'l' : return LEFT;
		case 'u' : return UP;
		case '1' : return UP|RIGHT;
		case '2' : return UP|RIGHT|DOWN;
		case '3' : return RIGHT|DOWN;
		case '4' : return RIGHT|DOWN|LEFT;
		case '5' : return DOWN|LEFT;
		case '6' : return DOWN|LEFT|UP;
		case '7' : return LEFT|UP;
		case '8' : return LEFT|UP|RIGHT;
		case 'h' : return LEFT|RIGHT;
		case 'v' : return UP|DOWN;
		case 'A' : return UP;
		case 'B' : return 0;
	}

	printf("Error: unknown character '%c'\n", c);
	return 0;
}

struct Node
{
	void init(char n_c, int n_row, int n_col)
	{
		c = n_c;
		row = n_row;
		col = n_col;
		init(arrows(c));
		empty = c == '.';
		end_point = c == 'B';
		error = ' ';
		distance = 0;
		from = ' ';
		solution = ' ';
	}
	void init(int arrows)
	{
		r.init(arrows & RIGHT); 
		d.init(arrows & DOWN);
		l.init(arrows & LEFT);
		u.init(arrows & UP);
	}
	
	int row;
	int col;
	char c;
	
	bool empty;
	bool end_point;
	
	Edge r;
	Edge d;
	Edge l;
	Edge u;
	
	char error;
	
	int distance;
	char from;
	char solution;
};

Node maze[HEIGHT][WIDTH];

char v1[HEIGHT][WIDTH];
char v2[HEIGHT][WIDTH];
char v3[HEIGHT][WIDTH];

char *solution[HEIGHT] =
{
	"                                         ",
	"                             DLLLLLLLL   ",
	"        DLLLLL      DLLLLLLLLL       U   ",
	"        D    U      D                U   ",
	"        D    U      D                U   ",
	"        D    U      D                U   ",
	"        D    ULLLLLLL                U   ",
	"      DLL                            U   ",
	"      D                 RRRRRRRRRRRRDU   ",
	"      D                 U           DU   ",
	"      D              RRRU           DU   ",
	"      D         RRD  UDL            DUL  ",
	"      DRD  RRRRRU D  UDU            D UL ",
	"      DURRRU      D  ULU            RRDU ",
	"      DU          RRRRRRRRD           DU ",
	"      DU                  D           DU ",
	"      DU     DLL          RRRD       DLU ",
	"      DULL   D U       DLLLLLL       D U ",
	"      RRDU   D U       D             D U ",
	"        DU   D U       D             D U ",
	"        DULLLL U       D   DLLLLLLLL D U ",
	"        D      U  DLLLLL   RRRRRD  ULL U ",
	"        D      U  D             D      U ",
	"       DL    RRU  D             RRRRRD U ",
	"       D     U    D   RRRRD          D U ",
	"    DL RD    U    D   U   D          D U ",
	"    DU  D RRRU    D   U   D       DLLL U ",
	"    DULLL U       RRRRU   D       D    U ",
	"    D     U               RRRRRRD RRRD U ",
	"  DLL     U                     D    D UL",
	"  RRRRRD  U      DLLLLLLL       RRD  D  U",
	"       D  U      D      ULLLLL    D  D  U",
	"       D  U DLLLLL           ULLL D  D  U",
	"       D RU D                   U D  RRDU",
	"       RRU  D         DLLLLLL   U D    DU",
	"            D      DLLLRRRRDULL ULL    DU",
	"     DLL    D      D   ULLLRRDULLLL    DU",
	"     D U    D   DLLD   DL U  RRRRDU    DU",
	"    DL ULLL D   D UL RDDU U  DL  DU    DU",
	"  DLL     ULL  DL    U DU UDLLULLDU    DU",
	"  D            DRD RDULLU UDRRRDUDU    RU",
	"  D            DUD URD RURUDU  DUDU      ",
	"  RRD          RURRU RRU UDLU  DUDU      ",
	"    D    RRDRRRRRRRDRRRRRUDRU  DULU      ",
	"    D    U DULLLLLLDU DLLLDU   D  U      ",
	"    RD RDU RRRRRRRURU D  ULU DLL  UL     ",
	"     RRUDU DLLLLLLLDLLLRRRRU DRRRD UDL   ",
	"     DLLLU RRRRD  UD   U     DU DL ULU   ",
	"     DRRRU   DLD  UDRRRUDLLLLLU RRRRRU   ",
	"  DLLLU    DLDUD  ULU   D     U          ",
	"  RRRRU    DULUL    U DLL RRD ULLLLL     ",
	"           D       RU D   U D      U DLL ",
	"           D       U  RD  U RRRRRRRU D U ",
	"        DLLLRRDRD  UL  D  ULL        D U ",
	"        RRD U DUD   U  D    ULLLLLLLLL U ",
	"          RRU RURRRRU  RRRRRRRRRRRRRRRRU ",
	"                                         ",
};

void fill()
{
	char (*v)[HEIGHT][WIDTH];
	
#define sl(X) for (int col = 0; col < WIDTH; col++) (*v)[row][col] = X[col]; row++;

	// First version from ArrowMaze.html
	
	v = &v1;
	int row = 0;

	sl("r........r........r...........r.......3.d")//1
	sl(".dh.d.lr.1.......d2r........dd.......l3d.")
	sl("...dl...d..5.ld..ld.d........h1.....d..dl")
	sl("....rd....r.d1.....u.r..3...r.1...dl5...l")
	sl("..............d.....5.rdr...v......75..rv")//5
	sl(".........1u...r...3..1ur......1.d.3.3.rd.")
	sl("..........ul.u......l.1vdl...l.l.5...72.d")
	sl("...ru.v7l...3..d.5..l..r.1....2v3...r.dl.")
	sl("uhud.l.r.u6..5...l.l....r1..........2..d5")
	sl("r.dl..4ldl...lr....2.....d.........l....l")//10
	sl("..r..d.ul1....u5...l.1112.........d...hrd")
	sl("..d..l3..1d....lr.d......3......dld..vl..")
	sl(".u....5rdulr....u...u7....r....d......u7.")
	sl("..r..d..r..u4....v.7.7lBr3ur..d...ruh.d..")
	sl("..d..l..d.75.....lr.3....33ud..l..1..d...")//15
	sl("..r..d...r..d...l..ll....l.7hud.lu7ldl...")
	sl("...v.l..ru...d.lu....lr..ur..d.u..7..5l..")
	sl("...r.d.u.l.r3.r.....1.udv....lr...u...l7.")
	sl("1uvlvlr.d.1...u1....u.....r........u.....")
	sl(".dl.r..d..7.l...r....u.....u.......7.....")//20
	sl("...u6..5.u7.55...r....u....d.......7r.v..")
	sl("..u7.rd.d..7.rv...d....l...r....drd......")
	sl("......d53.u.r.r1.u5v....l.u....l.u5...l..")
	sl(".r.1d..dl..7.h5uul.5...l.7....l.r....d...")
	sl("u..lru..5...l..rd...dlr...dr..uu..h.d....")//25
	sl("r..udl.rdr..u.......r..1.d..r...d..ll....")
	sl(".d.l..5.57r..u.....r.u..8...u...lld..l...")
	sl(".....u..l.1..d...uh...u.7r.u.....7.u..7..")
	sl("....3...u..d.l..r......u7lr.....d.r..du.l")
	sl("u.67h...v...7.l.r........u.....l.u.l...vl")//30
	sl("vlr....d...r...u.d......h..u..7.r.d......")
	sl("...d..l....r....u.v....lv....l.u.l.......")
	sl("...r.u......d....l.d..l..7.llu7.l.....ul.")
	sl("......u5h11u.r...u.ruru.r..uul.l.....r.d.")
	sl(".1...v.r.uru..v...h..udu....lur..u.u8.d..")//35
	sl("..d.h.1.dru....d...5..lr...dv.7.u.l......")
	sl("..rv.d.l............d..7..lr.duu..l..ul..")
	sl(".u.hu...ru....u.v5l.3u.5l....r...v..u.l..")
	sl("d.l.dl.u5.81.u.l..ul.rd......dh....u..7..")
	sl("d.67h.1d..v.h.udlrd.l.B....v.lu.l..r..u..")//40
	sl(".r.1..2....u..l.rd.rdu5l....r..d....u..hu")
	sl("..r1.r..r.r..u......rd.rv1u........u....l")
	sl("..3.d..r.1....uru3.u.r.u..dl.......r...u.")
	sl("......r.dr.dr......dr....u.ru...vl.u....7")
	sl(".....ul.l...7.....l...d..l..r....r.....d.")//45
	sl("..rvrd.rd.7h......uru....ul.u6.lruvlu.l..")
	sl(".u6.lr.u...d......ld..lr...u..1..d..vl...")
	sl("rd...d..l..r...3dl.5...1....u..d5l.ul....")
	sl("...r..1..u...5l.....r..vd....5..r.r..v...")
	sl("..d..l.d.l.d7.....ul.d.l.d...5.r....dru..")//50
	sl("..3...1..u..ulul......d.l.r.d.v7...lr..ru")
	sl("...d..h.....d...l..1u...l....r......ud5l.")
	sl(".....u.r..u3r..u.....drd....r......u.....")
	sl("..r...u.d..l1.vr3u.vl3d..lu.h.......u....")
	sl(".r.....ur3d..l....7l........u........l...")
	sl("v.......llr.u.rur...u..r1..............u.")//55
	sl("r.......u....7.......lr...............r.u")
	
	// Second version from ArrowMaze.html
	
	v = &v2;
	row = 0;

	sl("r........r........r...........r.......3.d")
	sl(".dh.d.lr.1.......31r........dd.......l3d.")
	sl("...dl...d..5.ld..hd.d........h1.....d..dl")
	sl("....rd....r.d1.....u.r..3...r.1...dl5...l")
	sl("..............d.....5.rdr...v......75..rv")
	sl(".........1u...r...3..1ur......1.d.3.3.rd.")
	sl("..........ul.u......l.1vdl...l.l.5...72.d")
	sl("...ru.v7l...3..d.5..l..r.1....2v3...r.dl.")
	sl("uhud.l.r.u6..5...l.l....r1..........2..d5")
	sl("r.dl..4udl...lr....2.....v..5......l....l")
	sl("..r..d.ul1....u5...l.1112.........d...hrd")
	sl("..d..l3..1d....lr.d...dl.3......dl...vl..")
	sl(".u....5rdulr....u...u7....r....d......u7.")
	sl("..r..d..r..u3....v.7.7lAr3ur..d...ruh.d..")
	sl("..d..l..d.75.....lr.3.....3ud..l..1..d...")
	sl("..r..d...r..d...l...l....l.7hud.lu775l...")
	sl("...v.l..ru...d.lu....lr..ur..d.u..7..5l..")
	sl("...r.d.u.l.r3.r.....1.ud6....lr...u...l7.")
	sl("1uvlvlr.d.1...u1....u.....r.......1u.....")
	sl(".dl.r..d....l...r....u.....u.......7.....")
	sl("...u6..5.u..55...r....u....d.......73.v..")
	sl("..u7.rd.d..7.rv...d....l...r....drdu.l...")
	sl("......d53.u.r.r..u.v....l.u....l.u5...l..")
	sl(".r.1d..dl..7.h3uul.5...l.7....l.r....d...")
	sl("u..lru..5...l..rd...dlr...dr..uu..h.d....")
	sl("r..udl.rdr..u.......r..1.d..r...d..ll....")
	sl(".d.l..5.57r..u.....r.u..8...u...lld..l...")
	sl(".....u..l.1..d...uh...u..r.u.....7.u..7..")
	sl("....3...u..d.l..r......u7lr.....d.r..du.l")
	sl("u.6.h...v...7.l.r........u.....l.u.l...vl")
	sl("vl3....d...r...u.d......h..u..7.r.d......")
	sl("...d.ll....r....u.v....lu....l.u.l.......")
	sl("...r.v......d....l.d..l..7.llu..l.....ul.")
	sl("..d..lu5.11u.r.....ruru.r..uul.l.....r.d.")
	sl(".1...u.r.uru..u...h..ud7....luh..u.u8.d..")
	sl("..d.h.1.dru....d...5..lr...dv.7.u.l......")
	sl("..rv.d.l........r...d..7..lr.duu..l..ul..")
	sl(".u.hu...ru....u.v5l.3u.5l....r...v..u.l..")//38
	sl("d.l.dl.u..8u.u.l..ul.r2......dh....u..7..")
	sl("d.67h.1d..u.l..dlrd.l.B.1..v.lu.l..r..u..")
	sl(".r.1..2....u..l.rd.rvu5l....r..3.d..u..hu")//41
	sl("..31....r.r..u......rd.rv1u........u....l")
	sl("..3.d..r.1....uru3.u.3.u..dl.......r...u.")
	sl("......r.dr.dr......dr....u.ru...vl.u....7")
	sl(".....ul.l...7.....l...d..l..r....r.....d.")
	sl("..rvrd.rd.uh......urud...7l..6.lruvlu.l..")
	sl(".u7.lr.u...d......ld..lr...u..1..d..vl...")
	sl("rd...d..l..r...3dl.5...8....u..dd5.ul....")//48
	sl("...ru.r..u...5l.....r..vd....l..3.r..v...")
	sl("..v..l.d.l.d7.....ul.d.l.d...5.r....dru..")
	sl("..3...u..u..ulul......d.l.r.d.u...5lr..ru")
	sl("...d..h.....d...l..ru...l....r......ud5l.")
	sl("...r.u.r..u3r...u....drd....r......u.....")//53
	sl("..r...u.d..lr.drdu.vl3d..lu.l.......u....")
	sl(".r.....ur.d..l....7l...d....7....l...l...")
	sl("v.......llr.u.rur...u..r1.......r.r....u.")
	sl("r.......u....7.......lr...............r.u")

	// Third version from ArrowMaze.html
	
	v = &v3;
	row = 0;

	sl("r........r........r...........r.......3.d")
	sl(".dh.d.lr.1.......32r........dd.......l3d.")
	sl("...dl...d..5.ld..hd.d........h1.....d..dl")
	sl("....rd....r.d1.....u.r..3...r.1...dl5...l")
	sl("..............d.....5.rdr...v......75..rv")//5
	sl(".........1u...r...3..1ur......1.d.3.3.rd.")
	sl("..........ul.u......l.1v.l...l.l.5...82.d")
	sl("...ru.v7l...3..d.5..l..r.1....2v3...r.dl.")
	sl("uhud.l.r.u6..5...lll....r1..........2..d5")
	sl("r.dl..4udl...lr....2.....d..5......l....l")//10
	sl("..r..d.ul1....u5...l.1112.........d...hrd")
	sl("..d..l3..1d....lr.d...dl.3......dl...vl..")
	sl(".u....5rdulr....u...u7....r....d......u7.")
	sl("..r..d..r..u3....v.7.7lAr3ur..d...ruh.d..")
	sl("..d..l..d.75.....lr.3.....3ud..l..1..d...")//15
	sl("..r..d...r..d...l...l....l.7hud.lu775l...")
	sl("...v.l..ru...d.lu....lr..ur..d.u..7..5l..")
	sl("...r.d.u.l.r3.r.....1.ud6....lr...u...l7.")
	sl("1uvlvlr.d.1...u1....u.....r.......1u.....")
	sl(".dl.r..d..7.l...r....u.....u.......7.....")//20
	sl("...u6..5.u..55...r....u....d.......73.v..")
	sl("..u7.rd.d..7.rv...d....l...r....drdu.l...")
	sl("......dl3.u.r.r1.u5v....l.u....l.u5...l..")
	sl(".r.1d..dl..7.h3uul.5...l.7....l.r....d...")
	sl("u..lru..5...l..rd...dlr...dr..uu..h.d....")//25
	sl("r..udl.rdr..u.......r..1.d..r...d..ll....")
	sl(".d.l..5.57r..u.....r.u..8...u...lld..l...")
	sl(".....u..l.1..d...uh...u..r.u.....7.u..7..")
	sl("....3...u..d.l..r......u7lr.....d.r..du.l")
	sl("u.67h...v...7.l.r........u.....l.u.l...vl")//30
	sl("vl3....d...r...u.d......h..u..7.r.d......")
	sl("...d.ll....r....u.v....lv....l.u.l.......")
	sl("...r.v......d....l.d..l..7.llu7.l.....ul.")
	sl("..d..lu5.11u.r.....ruru.r..uul.l.....r.d.")
	sl(".1...u.r.uru..u...h..ud7....luh..u.u8.d..")//35
	sl("..d.h.1.dru....d...5..lr...dv.7.u.l......")
	sl("..rv.d.l........r...d..7..lr.du7..l..ul..")
	sl(".u.hu...ru....u.v5l.3u.5l....r...v..u.l..")//38
	sl("d.l.dl.u5.81.u.l..ul.r2......dh....u..7..")
	sl("d.67h.1d..v.h.udlrd.l.B.1..v.lu.l..r..u..")
	sl(".r.1..2....u..l.rd.rvu5l....r..3.d..u..hu")//41
	sl("..31....r.r..u......rd.rv1u........u....l")
	sl("..3.d..r.1....uru3.u.3.u..dl.......r...u.")
	sl("......r.dr.dr......dr....u.ru...vl.u....7")
	sl(".....ul.l...7.....l...d..l..r....r.....d.")
	sl("..rvrd.rd.uh......urud...7l..6.lruvlu.l..")
	sl(".u7.lr.u...d......ld..lr...u..1..d..vl...")
	sl("rd...d..l..r...3dl.5...8....u..d55.ul....")//48
	sl("...ru.1..u...5l.....r..vd....5..3.r..v...")
	sl("..v..l.d.l.d7.....ul.d.l.d...5.r....dru..")
	sl("..3...1..u..ulul......d.l.r.d.u7..5lr..ru")
	sl("...d..h.....d...l..1u...l....r......ud5l.")
	sl("...r.u.r..u3r...u....drd....r......u.....")//53
	sl("..r...u.d..l1.vr3u.vl3d..lu.h.......u....")
	sl(".r.....ur3d.......7l...d....7....l...l...")
	sl("v.......llr.u.rur...u..r1.......r.r....u.")
	sl("r.......u............lr...............r.u")

	char v2_m[HEIGHT][WIDTH];
	for (int row = 0; row < HEIGHT; row++)
		for (int col = 0; col < WIDTH; col++)
			v2_m[row][col] = v2[row][col];

#define checkchange(R,C,F,T) if (v2[R-1][C-1] != F || v3[R-1][C-1] != T) printf("Error: Incorrect change %d,%d from %c to %c\n",R,C,F,T); else v2_m[R-1][C-1]=T;

	// An obvious error
	checkchange(37,32,'u','7')
	
	// Removing shorter paths:
	checkchange(9,19,'.','l')
	checkchange(23,8,'5','l')
	checkchange(55,14,'l','.')
	checkchange(57,14,'7','.')

	// Removing alternative solutions
	checkchange(7,25,'d','.')
	checkchange(10,26,'v','d')

	checkchange(7,38,'7','8')

	checkchange(2,19,'1','2')
	//checkchange(12,35,'.','d') -- introduces useless arrow
	//checkchange(16,20,'.','l') -- does not remove error, '7' even better
	checkchange(20,11,'.','7') // does not fix any error
	checkchange(23,16,'.','1') // does not fix any error
	checkchange(23,19,'.','5') // does not fix any error
	checkchange(30,4,'.','7') // makes 27,4 reachable
	checkchange(32,25,'u','v') // making 34,25 reachable
	checkchange(33,31,'.','7') // making 31,31 reachable
	checkchange(39,9,'.','5') // making 42,9 no longer useless
	checkchange(39,12,'u','1') // does not fix any error
	checkchange(40,11,'u','v') // does not fix any error
	checkchange(40,13,'l','h') // does not fix any error
	checkchange(40,15,'.','u') // does not fix any error
	//checkchange(42,6,'.','r') -- does not remove error, makes it more interesting
	//checkchange(46,29,'.','u') -- does not remove error, makes it more interesting
	checkchange(48,33,'d','5')  // Now 48,32 reachable
	checkchange(49,7,'r','1')   // Now 45,7 reachable
	checkchange(49,30,'l','5')  // Now 50,30 reachable
	checkchange(51,7,'u','1')   // Now 51,10 reachable
	checkchange(51,32,'.','7') // does not fix any error
	checkchange(52,20,'r','1') // does not fix any error
	checkchange(54,13,'r','1') // does not fix any error
	checkchange(54,15,'d','v') // does not fix any error
	checkchange(54,17,'d','3')  // Now 54,18 reachable
	checkchange(54,29,'l','h')
	checkchange(55,10,'.','3')  // Now 56,10 reachable

	// Remaining errors, that could be resolved
	// 38,15 (u) needless arrow:
	// 53,22 (d) needless arrow: could add some arrow to this one, from left/right
	
	for (int row = 0; row < HEIGHT; row++)
		for (int col = 0; col < WIDTH; col++)
			if (v2_m[row][col] != v3[row][col])
				printf("Error: Missing change %d,%d from %c to %c\n", row+1, col+1, v2_m[row][col], v3[row][col]);

	// Checking
	printf("start checking\n");
	for (int row = 0; row < HEIGHT; row++)
		for (int col = 0; col < WIDTH; col++)
			if (   v1[row][col] != v2[row][col]
			    || v1[row][col] != v3[row][col]
			    || v2[row][col] != v3[row][col])
			{
				if (v1[row][col] == v2[row][col])
					printf("%d,%d changed from %c to %c in corrected version\n", row+1, col+1, v2[row][col], v3[row][col]);
				else if (v2[row][col] == v3[row][col])
					printf("%d,%d changed from %c to %c in second version\n", row+1, col+1, v1[row][col], v2[row][col]);
				else if (v1[row][col] == v3[row][col])
					printf("%d,%d corrected error (from %c to %c) from second version in last version\n", row+1, col+1, v1[row][col], v2[row][col]);
				else
					printf("%d,%d all different: %c %c %c\n", row+1, col+1, v1[row][col], v2[row][col], v3[row][col]);
			}
	printf("end checking\n");
}

void print()
{
	for (int row = 0; row < HEIGHT; row++)
	{
		for (int col = 0; col < WIDTH; col++)
			printf("%c%c", maze[row][col].c, maze[row][col].error);
		printf("\n");
	}
}

void print_sol()
{
	printf("-\n");
	for (int row = 0; row < HEIGHT; row++)
	{
		for (int col = 0; col < WIDTH; col++)
			printf("%c", maze[row][col].solution);
			//printf("%c%c", maze[row][col].c, maze[row][col].solution);
		printf("\n");
	}
}

void connect()
{
	for (int row = 0; row < HEIGHT; row++)
	{
		for (int col = 0; col < WIDTH; col++)
		{
			Node &node = maze[row][col];
			
			// right
			if (node.r.out)
			{
				int col2;
				for (col2 = col + 1; col2 < WIDTH; col2++)
				{
					if (!maze[row][col2].empty)
					{
						Node &node_to = maze[row][col2];
						node.r.to = &node_to;
						node_to.l.from = &node;
						node.r.len = col2 - col;
						break;
					}
				}
			}
			
			// down
			if (node.d.out)
			{
				int row2;
				for (row2 = row + 1; row2 < HEIGHT; row2++)
				{
					if (!maze[row2][col].empty)
					{
						Node &node_to = maze[row2][col];
						node.d.to = &node_to;
						node_to.u.from = &node;
						node.d.len = row2 - row;
						break;
					}
				}
			}

			// left
			if (node.l.out)
			{
				int col2;
				for (col2 = col - 1; col2 >= 0; col2--)
				{
					if (!maze[row][col2].empty)
					{
						Node &node_to = maze[row][col2];
						node.l.to = &node_to;
						node_to.r.from = &node;
						node.l.len = col - col2;
						break;
					}
				}
			}
			
			// up
			if (node.u.out)
			{
				int row2;
				for (row2 = row - 1; row2 >= 0; row2--)
				{
					if (!maze[row2][col].empty)
					{
						Node &node_to = maze[row2][col];
						node.u.to = &node_to;
						node_to.d.from = &node;
						node.u.len = row - row2;
						break;
					}
				}
			}
		}
	}	
}

int error_go_no_where;
int error_not_reachable;
int error_collide;
int error_needless;
int error_alternative_path;
int error_wrong_solution;

bool trace_expand = true;

void check()
{
	for (int row = 0; row < HEIGHT; row++)
	{
		for (int col = 0; col < WIDTH; col++)
		{
			Node &node = maze[row][col];
			
			if (node.r.out && node.r.to == 0)
			{
				printf("Error: %d,%d (%c) right goes to nothing\n", row+1, col+1, node.c);
				node.error = '*';
				error_go_no_where++;
			}
			if (node.d.out && node.d.to == 0)
			{
				printf("Error: %d,%d (%c) down goes to nothing\n", row+1, col+1, node.c);
				node.error = '*';
				error_go_no_where++;
			}
			if (node.l.out && node.l.to == 0)
			{
				printf("Error: %d,%d (%c) left goes to nothing\n", row+1, col+1, node.c);
				node.error = '*';
				error_go_no_where++;
			}
			if (node.u.out && node.u.to == 0)
			{
				printf("Error: %d,%d (%c) up goes to nothing\n", row+1, col+1, node.c);
				node.error = '*';
				error_go_no_where++;
			}
			
			if (!node.empty || node.end_point)
			{
				if (node.r.from == 0 && node.d.from == 0 && node.l.from == 0 && node.u.from == 0)
				{
					printf("Error: %d,%d (%c) not reachable\n", row+1, col+1, node.c);
					node.error = '#';
					error_not_reachable++;
				}
			}
			if (node.r.to != 0 && node.r.from != 0)
			{
				printf("Error: %d,%d colide to the right\n", row+1, col+1);
				node.error = '@';
				error_collide++;
			}
			if (node.d.to != 0 && node.d.from != 0)
			{
				printf("Error: %d,%d colide to the bottom\n", row+1, col+1);
				node.error = '@';
				error_collide++;
			}
			if (!node.empty)
			{
				if (   (node.c == 'r' && node.r.from == 0 && node.d.from == 0 && node.l.from != 0 && node.u.from == 0)
				    || (node.c == 'l' && node.r.from != 0 && node.d.from == 0 && node.l.from == 0 && node.u.from == 0)
				    || (node.c == 'u' && node.r.from == 0 && node.d.from != 0 && node.l.from == 0 && node.u.from == 0)
				    || (node.c == 'd' && node.r.from == 0 && node.d.from == 0 && node.l.from == 0 && node.u.from != 0))
				{
					printf("Error: %d,%d (%c) needless arrow\n", row+1, col+1, node.c);
					node.error = '+';
					error_needless++;			
				}
			}
		}
	}
}

Node* start_node()
{
}

void add(Node* node, int distance, char from, int &max_distance)
{
	if (node != 0 && (node->distance == 0 || distance < node->distance))
	{
		if (distance > max_distance)
			max_distance = distance;
		node->from = from;
		node->distance = distance;
	}
}

void expand(Node* node, int &max_distance)
{
	if (trace_expand)
		printf(" %d,%d", node->row, node->col);
	add(node->r.to, node->distance + node->r.len, 'l', max_distance);
	add(node->d.to, node->distance + node->d.len, 'u', max_distance);
	add(node->l.to, node->distance + node->l.len, 'r', max_distance);
	add(node->u.to, node->distance + node->u.len, 'd', max_distance);
}		

void add_2(Node* node, int distance, char from, bool from_solution, bool &changed)
{
	if (node != 0)
	{
		if (node->solution == ' ')
		{
			if (node->distance < distance)
			{
				//printf(" %d,%d (%d)", node->row, node->col, node->distance);
				node->distance = distance;
				changed = true;
			}
		}
		else if (!from_solution && distance < node->distance)
		{
			printf("Error: %d,%d alternative path coming from %c at distance %d to %d\n", node->row, node->col, from, distance, node->distance);
			node->error = '&';
			error_alternative_path++;
		}
	}
}

void expand_2(Node* node, bool &changed)
{
	bool from_solution = node->solution != ' ';
	add_2(node->r.to, node->distance, 'l', from_solution, changed);
	add_2(node->d.to, node->distance, 'u', from_solution, changed);
	add_2(node->l.to, node->distance, 'r', from_solution, changed);
	add_2(node->u.to, node->distance, 'd', from_solution, changed);
}		

void solve(char (&v)[HEIGHT][WIDTH])
{
	for (int row = 0; row < HEIGHT; row++)
		for (int col = 0; col < WIDTH; col++)
			maze[row][col].init(v[row][col], row, col);

	error_go_no_where = 0;
	error_not_reachable = 0;
	error_collide = 0;
	error_needless = 0;
	error_alternative_path = 0;	
	error_wrong_solution = 0;
	
	connect();
	check();

	Node* start_node = 0;
	Node* end_node = 0;
	
	for (int row = 0; row < HEIGHT; row++)
	{
		for (int col = 0; col < WIDTH; col++)
		{
			if (maze[row][col].c == 'A')
				start_node = &maze[row][col];
			if (maze[row][col].c == 'B')
				end_node = &maze[row][col];
		}
	}

	if (start_node == 0)
	{
		printf("Error: No start node\n");
		return;
	}
	if (end_node == 0)
	{
		printf("Error: No end node\n");
		return;
	}

	int max_distance = 0;
	expand(start_node, max_distance);
	for (int distance = 1; distance <= max_distance; distance++)
	{
		if (trace_expand)
			printf("%d: ", distance);
		for (int row = 0; row < HEIGHT; row++)
			for (int col = 0; col < WIDTH; col++)
				if (maze[row][col].distance == distance)
					expand(&maze[row][col], max_distance);
		if (trace_expand)
			printf("\n");
	}

	// Track back
	for (Node *node = end_node; node != start_node; )
	{
		int row = node->row;
		int col = node->col;
		switch (node->from)
		{
			case 'r':
				node = node->r.from;
				for (col++; col <= node->col; col++)
					maze[row][col].solution = 'L';
				break;
			case 'd':
				node = node->d.from;
				for (row++; row <= node->row; row++)
					maze[row][col].solution = 'U';
				break;
			case 'l':
				node = node->l.from;
				for (col--; col >= node->col; col--)
					maze[row][col].solution = 'R';
				break;
			case 'u':
				node = node->u.from;
				for (row--; row >= node->row; row--)
					maze[row][col].solution = 'D';
				break;
			default:
			{
				printf("Error: trace back\n");
				return;
			}
		}
	}
	
	// Now check all other paths to see if they do not lead to the end point
	for (int row = 0; row < HEIGHT; row++)
		for (int col = 0; col < WIDTH; col++)
		{
			Node& node = maze[row][col];
			if (node.solution == ' ')
				node.distance = 0;
		}
		
	for (int distance = 1; distance <= max_distance; distance++)
	{
		bool changed;
		do
		{
			changed = false;
			
			//printf("%d: ", distance);
			for (int row = 0; row < HEIGHT; row++)
				for (int col = 0; col < WIDTH; col++)
					if (maze[row][col].distance == distance)
						expand_2(&maze[row][col], changed);
			//printf("\n");
		}
		while (changed);
	}

	for (int row = 0; row < HEIGHT; row++)
		for (int col = 0; col < WIDTH; col++)
			if (maze[row][col].solution != solution[row][col])
				error_wrong_solution++;

	printf("errors: %d %d %d %d %d %d\n",
		error_go_no_where,
		error_not_reachable,
		error_collide,
		error_needless,
		error_alternative_path,
		error_wrong_solution);
}

int main(int argc, char *argv[])
{
	fill();
	solve(v3);
	print();
	print_sol();
	printf("\n---\n");

	trace_expand = 0;
		
	char error[HEIGHT][WIDTH];
	for (int row = 0; row < HEIGHT; row++)
		for (int col = 0; col < WIDTH; col++)
			error[row][col] = maze[row][col].error;

	char corrections[HEIGHT][WIDTH];
	for (int row = 0; row < HEIGHT; row++)
		for (int col = 0; col < WIDTH; col++)
			corrections[row][col] = ' ';	
				
	for (int row = 0; row < HEIGHT; row++)
		for (int col = 0; col < WIDTH; col++)
		{
			int arrows_v1 = arrows(v1[row][col]);
			int arrows_v2 = arrows(v2[row][col]);
			int arrows_v3 = arrows(v3[row][col]);
			
			if (arrows_v3 == arrows_v2 && arrows_v1 != arrows_v2 && (arrows_v1 & arrows_v2) == arrows_v2)
			{
				char v3_corrected[HEIGHT][WIDTH];
				
				for (int r = 0; r < HEIGHT; r++)
					for (int c = 0; c < WIDTH; c++)
						v3_corrected[r][c] = v3[r][c];
				v3_corrected[row][col] = v1[row][col];
				
				printf("\n\nTrying correcting %d,%d from %c to %c\n", row+1, col+1, v3[row][col], v1[row][col]);
				
				solve(v3_corrected);
				
				if (   error_wrong_solution == 0 
					&& error_go_no_where == 0
					&& error_collide == 0
					&& error_alternative_path == 0)
				{
					for (int r = 0; r < HEIGHT; r++)
						for (int c = 0; c < WIDTH; c++)
							if (maze[r][c].error != error[r][c])
								printf("%d,%d error from '%c' to '%c'\n", r+1, c+1, error[r][c], maze[r][c].error);
					printf("Correcting %d,%d from %c to %c is good\n", row+1, col+1, v3[row][col], v1[row][col]);
					corrections[row][col] = v1[row][col];					
				}
				else
				{
					if (error_wrong_solution > 0)
						printf("Solution is different on %d points\n", error_wrong_solution);
					if (error_go_no_where > 0)
						printf("Go no where: %d\n", error_go_no_where);
					if (error_collide > 0)
						printf("Collides: %d\n", error_collide);
					if (error_alternative_path > 0)
						printf("Alternative paths found: %d\n", error_alternative_path);
					printf("Correcting %d,%d from %c to %c is bad\n", row+1, col+1, v3[row][col], v1[row][col]);
				}
			}
			
		}	

	for (int row = 0; row < HEIGHT; row++)
		for (int col = 0; col < WIDTH; col++)
			if (corrections[row][col] != ' ')
			{
				printf("\tcheckchange(%d,%d,'%c','%c')\n", row+1, col+1, v2[row][col], corrections[row][col]);
			}
	printf("\n");
	for (int row = 0; row < HEIGHT; row++)
	{
		printf("\tsl(\"");
		for (int col = 0; col < WIDTH; col++)
			printf("%c", corrections[row][col] != ' ' ? corrections[row][col] : v3[row][col]);
		printf("\")\n");
	}

	{
		char v3_corrected[HEIGHT][WIDTH];
		
		for (int r = 0; r < HEIGHT; r++)
			for (int c = 0; c < WIDTH; c++)
				v3_corrected[r][c] = corrections[r][c] != ' ' ? corrections[r][c] : v3[r][c];
		
		printf("\n\nTrying all corrections\n");
		
		solve(v3_corrected);
		
		if (   error_wrong_solution == 0 
			&& error_go_no_where == 0
			&& error_collide == 0
			&& error_alternative_path == 0)
		{
			for (int r = 0; r < HEIGHT; r++)
				for (int c = 0; c < WIDTH; c++)
					if (maze[r][c].error != error[r][c])
						printf("%d,%d error from '%c' to '%c'\n", r+1, c+1, error[r][c], maze[r][c].error);
			printf("All corrections are good\n");
		}
		else
		{
			if (error_wrong_solution > 0)
				printf("Solution is different on %d points\n", error_wrong_solution);
			if (error_go_no_where > 0)
				printf("Go no where: %d\n", error_go_no_where);
			if (error_collide > 0)
				printf("Collides: %d\n", error_collide);
			if (error_alternative_path > 0)
				printf("Alternative paths found: %d\n", error_alternative_path);
			printf("All corrections are bad\n");
		}
	}
}