#include <stdlib.h>
#include <stdio.h>

int **lab;
int **path;
int lrow, lcol;
int start_x, start_y, finish_x, finish_y;

void LoadIt(const char *filename);
void Dowave(int x, int y, int countofwave);
void FindPath(int x, int y, int countofwave);
void MergeIt();
void SaveIt(const char *filename);

void LoadIt(const char *filename){
	FILE *input = fopen(filename, "r");
	if (input == NULL){
		printf("Cannot open input file \n");
		exit(0);
	}
	else{
		fscanf(input, "%d%d", &lrow, &lcol);
		lab = (int **)malloc(lcol*sizeof(int *));
		path = (int **)malloc(lcol*sizeof(int *));
		for (int i = 0; i < lcol; i++){
			lab[i] = (int *)malloc(lrow *sizeof(int));
			path[i] = (int *)malloc(lrow *sizeof(int));
		}
		for (int i = 0; i < lcol; i++){
			for (int j = 0; j < lrow; j++){
				fscanf(input, "%d", &lab[i][j]);
				if (lab[i][j] == 1)
					lab[i][j] = -1;
				if (lab[i][j] == 2){
					start_y = j;
					start_x = i;
					lab[i][j] = 0;
				}
				if (lab[i][j] == 3){
					finish_y = i;
					finish_x = j;
					lab[i][j] = 0;
				}
			}
		}
	}
	fclose(input);
}

void Dowave(int x, int y, int countofwave){
	lab[x][y] = countofwave;
	if (y + 1 < lrow){
		if ((lab[x][y + 1] == 0) || ((lab[x][y + 1] != -1) && (lab[x][y + 1] > countofwave))){
			Dowave(x, y + 1, countofwave + 1);
		}
	}
	if (x + 1 < lcol){
		if ((lab[x + 1][y] == 0) || ((lab[x + 1][y] != -1) && (lab[x + 1][y] > countofwave))){
			Dowave(x + 1, y, countofwave + 1);
		}
	}
	if (y - 1 >= 0){
		if ((lab[x][y - 1] == 0) || ((lab[x][y - 1] != -1) && (lab[x][y - 1]> countofwave))){
			Dowave(x, y - 1, countofwave + 1);
		}
	}
	if (x - 1 >= 0){
		if ((lab[x - 1][y] == 0) || ((lab[x - 1][y] != -1) && (lab[x - 1][y] > countofwave))){
			Dowave(x - 1, y, countofwave + 1);
		}
	}
}

void FindPath(int x, int y, int countofwave){
	path[x][y] = 666;
	if (y + 1 < lrow){
		if ((lab[x][y + 1] == 0) || ((lab[x][y + 1] != -1) && (lab[x][y + 1] == countofwave - 1))){
			FindPath(x, y + 1, countofwave - 1);
		}
	}
	if (x + 1 < lcol){
		if ((lab[x + 1][y] == 0) || ((lab[x + 1][y] != -1) && (lab[x + 1][y] == countofwave - 1))){
			FindPath(x + 1, y, countofwave - 1);
		}
	}
	if (y - 1 >= 0){
		if ((lab[x][y - 1] == 0) || ((lab[x][y - 1] != -1) && (lab[x][y - 1] == countofwave - 1))){
			FindPath(x, y - 1, countofwave - 1);
		}
	}
	if (x - 1 >= 0){
		if ((lab[x - 1][y] == 0) || ((lab[x - 1][y] != -1) && (lab[x - 1][y] == countofwave - 1))){
			FindPath(x - 1, y, countofwave - 1);
		}
	}
}

void SaveIt(const char *filename){
	FILE *output = fopen(filename, "w+");
	for (int i = 0; i < lcol; i++){
		for (int j = 0; j < lrow; j++){
			if (i == start_x && j == start_y)
				fprintf(output, "S");
			else if (i == finish_y && j == finish_x)
				fprintf(output, "F");
			else{
				if (lab[i][j] == -1)
					fprintf(output, "1");
				if (path[i][j] == 666)
					fprintf(output, "*");
				if (path[i][j] != 666 && lab[i][j] != -1)
					fprintf(output, " ");
			}
		}
		fprintf(output,"\n");
	}
	fclose(output);
}

int main(){
	LoadIt("lab.txt");
	Dowave(start_x, start_y, 0);
	if (lab[start_y][finish_x] > 0){
		printf("possible \n");
		FindPath(finish_y, finish_x, lab[finish_y][finish_x]);
		SaveIt("result.txt");
	}
	else
		exit(0);
	free(lab);
	free(path);
	return 0;
}