#include<stdio.h>
#include<assert.h>

#define X 0

void main() {
	int m,n;
	FILE *F = fopen("input.txt","r");
	fscanf(F, "%d %d", &m, &n);
	assert(m>=0);
	assert(n>=0);
	char griglia[m][n];
	int pacman[m][n];
	int i,j;
	//inizializza matrice
	for(i=0;i<m;i++) {
		for(j=0;j<n;j++) {
			fscanf(F, " %c", &griglia[i][j]);
		}
		printf("\n");
	}
	fclose(F);
	
printf("\n stampo matrice \n");
for(j=0;j<m;j++) {
for(i=0;i<n;i++) {
printf("%c",griglia[j][i]);
}
printf("\n");
}

	//cerco il pacman
	int i_pac, j_pac;
	for(i=0;i<m;i++) {
		for(j=0;j<n;j++) {
			if (griglia[i][j]=='M') {
				i_pac=i;
				j_pac=j;
			}
		}
	}
	//creo la matrice distanza del pacman
	pacman[i_pac][j_pac]=0;
	//riga verso sinistra
	int contatore;
	contatore=1;
	for(j=(j_pac)-1;0<=j;j--) {
		pacman[i_pac][j]=contatore;
		contatore=contatore+1;
	}
	//riga verso destra
	contatore=1;
	for(j=(j_pac)+1;j<n;j++) {
		pacman[i_pac][j]=contatore;
		contatore=contatore+1;
	}
	//riga verso alto
	for(i=(i_pac)-1;0<=i;i--) {
		for(j=0;j<=n;j++) {
			pacman[i][j]=pacman[i+1][j]+1;
		}
	}
	//riga verso basso
	for(i=(i_pac)+1;i<=m;i++) {
		for(j=0;j<=n;j++) {
			pacman[i][j]=pacman[i-1][j]+1;
		}
	}

printf("\n stampo matrice pacman \n");
for(j=0;j<m;j++) {
for(i=0;i<n;i++) {
printf("%d ",pacman[j][i]);
}
printf("\n");
}

	//cerco la P più vicina
	int i_p, j_p;
	int min;
	min=10000;
	for(i=0;i<m;i++) {
		for(j=0;j<n;j++) {
			if (griglia[i][j]=='P') {
				if (pacman[i][j]<min) {
					i_p=i;
					j_p=j;
					min=pacman[i][j];
				}
			}
		}
	}
printf("\n P trovato in %d %d\n", i_p,j_p);

	//per ogni fantasmino creo la sua matrice e la confronto con quella del pacman
	//conta i fantasmi
	int n_fantasmi;
	int conflitto;
	n_fantasmi=0;
	for(i=0;i<m;i++) {
		for(j=0;j<n;j++) {
			if (griglia[i][j]=='F') n_fantasmi=n_fantasmi+1;
		}
	}
printf("ho trovato %d fantasmi\n",n_fantasmi);
	int k;
	for(k=0;k<n_fantasmi;k++){
		//cerco quello più vicino
		int i_fan, j_fan;
		int min;
		min=10000;
		for(i=0;i<m;i++) {
			for(j=0;j<n;j++) {
				if (griglia[i][j]=='F') {
					if (pacman[i][j]<min) {
						i_fan=i;
						j_fan=j;
						min=pacman[i][j];
					}
				}
			}
		}
printf("trovato in %d %d\n",i_fan, j_fan);
		//creo la matrice distanza del fantasma
		int fantasma[m][n];
		fantasma[i_fan][j_fan]=0;
		//riga verso sinistra
		contatore=1;
		for(j=(j_fan)-1;0<=j;j--) {
			fantasma[i_fan][j]=contatore;
			contatore=contatore+1;
		}
		//riga verso destra
		contatore=1;
		for(j=(j_fan)+1;j<n;j++) {
			fantasma[i_fan][j]=contatore;
			contatore=contatore+1;
		}
		//riga verso alto
		for(i=(i_fan)-1;0<=i;i--) {
			for(j=0;j<=n;j++) {
				fantasma[i][j]=fantasma[i+1][j]+1;
			}
		}
		//riga verso basso
		for(i=(i_fan)+1;i<=m;i++) {
			for(j=0;j<=n;j++) {
				fantasma[i][j]=fantasma[i-1][j]+1;
			}
		}

printf("\n stampo matrice fantasma \n");
for(j=0;j<m;j++) {
for(i=0;i<n;i++) {
printf("%d ",fantasma[j][i]);
}
printf("\n");
}

		//guardo se con lo stesso numero di mosse possono occupare la stessa cella
		conflitto=0;
		for(i=0;i<m;i++) {
			for(j=0;j<n;j++) {
				if (pacman[i][j]==fantasma[i][j]) {
					conflitto=1;
				}
			}
		}
		







		//libero la cella per non trovarlo più
		griglia[i_fan][j_fan]='L';
		
	}
	
	
	
	
printf("\nconflitto è a %d\n",conflitto);



		F = fopen("output.txt","w");
		if (conflitto==1) fprintf(F, "%d", 0);
		else fprintf(F, "%d", 1);  //al posto di 1 conto i tipi di percorso
		fclose(F);
		
}