尼斯湖水怪是一隻住在尼斯湖中神秘且不明的動物。尼斯湖則是北蘇格蘭的印芬尼斯市附近的一個大且深的淡水湖。尼斯怪通常被視為一種湖怪。
http://en.wikipedia.org/wiki/Loch_Ness_Monster

背景

2003 年 7 月，BBC (英國國家廣播電視公司) 曾報導了一項他們對尼斯湖所作的大規模研究，他們用 600 支聲納也沒有辦法在湖中找到任何「水怪」(也就是任何已知或未知的大型動物) 的踪跡。他們推論尼斯怪並不存在。現在我們要重覆這項實驗。

問題

給你一個 n 列 m 行的格子代表尼斯湖，6 ≤ n, m ≤ 10000，找出最少要放幾個聲納才能控制所有的方格，條件如下：

• 一個聲納佔一格；它的監控範圍為所在的那一格及緊鄰的格子；
• 邊緣的格子不需要監控，因為尼斯怪太大了，無法蔵在那兒。

例如， 

 其中 X 代表聲納，灰色區域則是它所監控的範圍。最後一個圖則是一組可接受的解答。