/*
ID: fniksic001
PROG: maze1
LANG: C
*/

#include <stdio.h>

#define maxw 38
#define maxh 100
#define maxexits 2
#define queuelength 10000
#define infinity 1<<30

typedef struct {
	int x,y;
} vertex;

/* our maze is stored as a bunch of characters
   w is the width, and h is the height of the maze */
char maze[2*maxh+1][2*maxw+3];
int w,h;

vertex exitmaze[maxexits];

int best[maxh][maxw]; /* this stores shortest paths from vertices to exits */

/* variables needed for the queue */
vertex queue[queuelength];
int head,tail;

/* functions that operate the queue */
void initq(void) {
	head=tail=0;
}

int qempty(void) {
	return head==tail;
}

void enq(vertex v) {
	queue[tail++]=v;
}

vertex deq(void) {
	return queue[head++];
}
/**/

void read_maze(void) {
	FILE *in;
	int i=0,j=0;
	char c;

	in=fopen("maze1.in","r");
	fscanf(in,"%d %d\n",&w,&h);
	while (fscanf(in,"%c",&c)!=EOF) {
		if (c=='+' || c=='-' || c==' ' || c=='|') maze[i][j++]=c;
		else if (c=='\n') {i++;j=0;}
	}
	fclose(in);
}
	
void locate_exits(void) {
	int i,nexits=0;

	/* check the top and the bottom wall */
	for (i=0;i<w;i++) {
		if (maze[0][2*i+1]==' ') {
			exitmaze[nexits].x=0;
			exitmaze[nexits].y=i;
			nexits++;
		}
		if (maze[2*h][2*i+1]==' ') {
			exitmaze[nexits].x=h-1;
			exitmaze[nexits].y=i;
			nexits++;
		}
	}
	/* check the left and the right wall */
	for (i=0;i<h;i++) {
		if (maze[2*i+1][0]==' ') {
			exitmaze[nexits].x=i;
			exitmaze[nexits].y=0;
			nexits++;
		}
		if (maze[2*i+1][2*w]==' ') {
			exitmaze[nexits].x=i;
			exitmaze[nexits].y=w-1;
			nexits++;
		}
	}
}

void do_an_exit(vertex e) {
	int temp[maxh][maxw];
	int i,j;
	vertex v,a;
	vertex d[]={{-1,0},{1,0},{0,-1},{0,1}}; /* directions */
	
	for (i=0;i<h;i++)
		for (j=0;j<w;j++)
			temp[i][j]=infinity;
	initq();
	
	temp[e.x][e.y]=1;
	enq(e);
	while(!qempty()) {
		v=deq();
		for (i=0;i<4;i++) {
			a.x=v.x+d[i].x;
			a.y=v.y+d[i].y;
			if (a.x>=0 && a.x<h && a.y>=0 && a.y<w && maze[2*a.x+1-d[i].x][2*a.y+1-d[i].y]==' ' && temp[a.x][a.y]==infinity) {
				temp[a.x][a.y]=temp[v.x][v.y]+1;
				enq(a);
			}
		}
	}
	
	/* So, we have shortest paths from each point in the maze to the
	   exit e. Now we have to check for every point v if the shortest
	   path from v to e is also the shortest path from v to any exit. */
	for (i=0;i<h;i++)
		for (j=0;j<w;j++)
			if (temp[i][j]<best[i][j]) best[i][j]=temp[i][j];
}
	
void write_solution(void) {
	FILE *out;
	int i,j,max=0;

	for (i=0;i<h;i++)
		for (j=0;j<w;j++)
			if (best[i][j]>max) max=best[i][j];

	out=fopen("maze1.out","w");
	fprintf(out,"%d\n",max);
	fclose(out);
}

int main(void) {
	int i,j;
	
	read_maze();
	locate_exits();
	
	for (i=0;i<h;i++)
		for (j=0;j<w;j++)
			best[i][j]=infinity;
	
	for (i=0;i<maxexits;i++) do_an_exit(exitmaze[i]);
	write_solution();
	
	return 0;
}