Problem : 269 - Mecho

大熊米可發現一個小寶藏 ─ 神秘蜜蜂的秘密蜂蜜罈！他開心地享用起新發現的寶藏，直到忽然間有一隻蜜蜂發現了他並且發出蜜蜂警報。他知道，從此刻起蜂巢裡的蜜蜂將傾巢而出並開始圍捕他。他得離開蜂蜜罈然後趕快回家；但是，蜂蜜實在是太美味了，所以他並不想那麼快離開。請幫忙米可決定他來得及離開蜂蜜罈的最晚時間點。

米可住的森林是由 N x N 個單位方格所形成的網格來表示，而方格的邊正好是南北向和東西向。每個單位方格可能是大樹方格、草叢方格、蜂巢方格、或米可的家。當一個方格從東邊、西邊、南邊或北邊 (不包含對角線) 緊鄰著另一個方格，我們將這兩個方格視為相鄰。米可是隻笨拙的熊，所以他的每一步必須移動到相鄰的方格。米可只能踏過草叢方格而無法跨過大樹或蜂巢方格；此外，每分鐘他最多只能移動S步。

在蜜蜂警報響起的那一刻，米可的位置是在蜂蜜罈所在的草叢方格，而蜂群則位在每一個蜂巢方格 (森林裡可能有多於一個蜂巢方格)。從這一刻開始的每一分鐘，下列的事件會依序發生：

　•假設米可正在享用蜂蜜，他要決定是否繼續享用或者離開。假如他繼續享用，這一分鐘內他都不會離開，否則，他會立刻離開並且在森林裡依照上述的方式移動至多S步。米可沒有辦法帶著蜂蜜移動，所以一旦他開始移動了，就再也吃不到蜂蜜了。

　•在米可食用蜂蜜或者移動了完整一分鐘後，蜂群會往草叢方格漫延一個單位。更精確地來說，蜂群會漫延至與他們佔據的方格相鄰的每一個草叢方格。除此之外，一旦方格被蜂群佔據，他就永遠都被佔據了。(也就是說，蜂群不是移動，而是不斷擴大佔據的範圍)

換句話說蜂群是這樣漫延的：一開始蜜蜂警報響起時，蜂群只佔據蜂巢所在的方格。在第一分鐘結束的時候，他們將佔據所有與蜂巢方格相鄰的草叢方格 (這當然也包括蜂巢方格所在的方格) 。在第二分鐘結束的時候，他們會再多佔據了所有與前述方格相鄰的草叢方格，以此類推。在足夠長的時間之後，蜂群會佔據所有他們到得了的草叢方格。

米可和蜂群都無法離開森林。還有，根據上述的規則，米可食用蜂蜜的時間一定是一個整數值。

當米可處於一個被蜜蜂佔據的方格，這代表米可被蜂群追到了。

給定森林的地圖，寫一個程式計算米可能夠留在他的初始位置食用蜂蜜的最大分鐘數，前提是他能在任何蜜蜂追到他之前回到他的家中。

Sample #1:
在食用蜂蜜一分鐘後，米可可以在兩分鐘內，直接往右走最短路徑躲過蜂群而安全返家。

Sample #2:
在食用蜂蜜兩分鐘後，米可能夠在第三分鐘走→↑→，第四分鐘走→→→，第五分鐘走↓→，以安全返家。

評分資訊：
佔總分 40 分的測試資料中，N 不超過 60。