初めに
自分の理解のためにも、bfsを徹底的に噛み砕いて書こうと思って書きます。
アリ本で一回解いてそれっきりになっていたのでabcで撃沈しました。
復讐（？）のためにも完全な理解を獲得したいと思います。
問題
考え方
最短経路問題なので、bfsを使います。（他のやり方は知りません）
ただこの問題では開始地点が定まっていないので、**全ての開始時点でのパターンを考えていきました。**その中での最短距離の最大値を考えていきます。（条件がゆるいためこれでも間に合います）
bfs
bfsは幅優先探索といい、周囲を全て探索をしながら探索の深さの足並み揃えて探索をしていくような探索です。
具体的には次のような感じになります。開始地点は左上としていることに注意してみてください。
灰色のは壁です。
一つずつ周りを探索しながらそこに未探索の経路があったら進んでいき現在のdの値（進行度合い）を入力していきます。
一番大事なのはそこに未探索経路がある時はその経路の座標をキューに一時的に保存していくということです。
具体的に見ていきます。
進行度合い（開始地点からの最短距離）d＝０では次のようになります。
周囲の未探索の経路は(0,1)(1,0)です。**その座標はキューに一時的に保存して次に生かしていきます。**上や左は経路が存在しないので除外されます。
進行度合いd=1では（0,2）(2,0)が未探索の経路です。
除外される経路についてここで言っておきたいと思います。
①そもそも空間が存在していない（座標範囲外）。
②そこに壁が存在する。
③そこはすでに探索済。
この３パターンです。プログラム上でこの３パターンは除外する必要があるので注意してください。
ここでは初期値として、壁のときの値を−１、未探索の値をinf(十分に大きい数)とします。
なのでこの三つについては、こうやって除外していきます。
①そもそも空間が存在していない（座標範囲外）→その座標が座標範囲内のみ探索
②そこに壁が存在する→その座標の値が−１なら除外
③そこはすでに探索済→その座標の値がinfでの場合のみ探索
d=8ではキューに保存する座標はなくなりループを終了する。
これくらいわかっておけばこの問題を解くのには十分です。
大まかな解法をもう一度確認
入力→
その開始時点からすべてにおいて、bfsする→
bfsしてその中のmaxのdを返す→
全ての開始時点でのmaxを出力する
という感じです。コードにすると以下の通り
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
# define rep(k,i,n) for(ll i=k;i<n;++i)
const ll inf=1e6;
ll c0[20][20],c1[20][20][20][20];//c0は入力の値を保存、c1は開始地点を変えながらbfsをしたときそれぞれの座標のd（最短距離）を保存するための配列
ll h,w;//座標の大きさ
int main(void){
cin>>h>>w;//座標の大きさの入力
rep(0,i,h){
string s0;
cin>>s0;
rep(0,j,w){
string s1=s0.substr(j,1);//座標ごとの文字をs1に入力
if(s1=="#"){
c0[i][j]=-1;//壁があるとき、c0に-1を入力
}else{
c0[i][j]=inf;//未探索の印にc0にinfを入力
}
}
}
ll ans=0;//答えの初期化
rep(0,i0,h){
rep(0,j0,w){
rep(0,i1,h){
rep(0,j1,w){
c1[i0][j0][i1][j1]=c0[i1][j1];//c0によりc1を初期化、(i0,j0)は開始地点。
}
}
ans=max(bfs(i0,j0),ans);//それぞれの開始地点においてbfsをし、最大値をとる。
}
}
cout<<ans<<endl;
}
全体の流れがわかりやすいように、main関数だけ書いています。
あとは関数bfs()を追加するだけです。開始地点を入力すると、全ての範囲の最短距離の最大値が返ってくるような関数です。（開始地点が壁であれば返ってくる値は０とする）
解答のコード
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
# define rep(k,i,n) for(ll i=k;i<n;++i)
const ll inf=1e6;
ll c0[20][20],c1[20][20][20][20];//c0は入力の値を保存、c1は開始地点を変えながらbfsをしたときそれぞれの座標のd（最短距離）を保存するための配列
ll dx[4]={0,0,1,-1},dy[4]={-1,1,0,0};//周辺を探索するときの座標変化
ll h,w;
ll bfs(ll sx,ll sy){
if(c0[sx][sy]==-1)return 0;//開始地点が壁の時は0を返す。
ll res=0;//最短距離の最大値の初期化
ll d=0;//最短距離の値の初期化
c1[sx][sy][sx][sy]=d;//スタート地点の初期化
queue<P> que;//未探索の次に探索する座標を保存させるためのqueue
que.push(P(sx,sy));//スタート地点の座標をqueueに保存
while(!que.empty()){//bfsが終わったらqueueにはいる座標はなくなるので、queueになくなるまでループを繰り返す
P p=que.front();que.pop();//queueを取り出す。
rep(0,i,4){
ll nx=p.first+dx[i],ny=p.second+dy[i];//多分now_xの略、今現在見ている座標を意味する。
if(0<=nx && h>nx && 0<=ny && w>ny){//範囲内の座標の条件
ll d=c1[sx][sy][nx][ny];
if(d==inf){//未探索の条件
que.push(P(nx,ny));//次の探索範囲に追加
c1[sx][sy][nx][ny]=c1[sx][sy][p.first][p.second]+1;//最短距離をc1に入れる
res=max(c1[sx][sy][nx][ny],res);//ここまでの最大値を入力
}
}
}
}
return res;
}
int main(void){
cin>>h>>w;//座標の大きさの入力
rep(0,i,h){
string s0;
cin>>s0;
rep(0,j,w){
string s1=s0.substr(j,1);//座標ごとの文字をs1に入力
if(s1=="#"){
c0[i][j]=-1;//壁があるとき、c0に-1を入力
}else{
c0[i][j]=inf;//未探索の印にc0にinfを入力
}
}
}
ll ans=0;//答えの初期化
rep(0,i0,h){
rep(0,j0,w){
rep(0,i1,h){
rep(0,j1,w){
c1[i0][j0][i1][j1]=c0[i1][j1];//c0によりc1を初期化、(i0,j0)は開始地点。
}
}
ans=max(bfs(i0,j0),ans);//それぞれの開始地点においてbfsをし、最大値をとる。
}
}
cout<<ans<<endl;
}
失敗しやすいこと
僕がコンテスト中に失敗したのは、間違えて再帰でbfsをしようとしてしまい失敗しました。
再起でしようとすると、探索の深さの足並みを揃えながらするということができず深くまで入り込んでしまいます。それではbfs（幅優先探索）ではなくdfs(深さ優先探索)になってしまいます。
初めにも言いましたがqueueを使うことが大事になってきます。
あと、このプログラムを実装するときに失敗したことは、**開始地点が壁の時のbfs関数を０にした方がいいということに気づかなかったことです。**それでWAを出してしまいました。
みなさん些細なところなので気をつけてください。
終わりに
楽しかったので、また機会があれば記事を作っていきたいと思います。（予定）
予定は未定です（予防線）