容易发现，如果有解，答案一定不超过 $2$。

首先，如果不联通，那么答案一定是 $0$。

否则如果 $nm-c\le2$，必然无解。

否则如果存在一个位置能直接把图断开（割点），那就是 $1$。

否则就是 $2$。

考虑怎么建出一张「简化」的图。

对于找割点的部分，我们把每个点往外扩展两圈，如果内圈中有割点则为 $1$。容易证明这是对的。

最后唯一的问题在于怎么判最开始的图是否联通。。

方法很简单，我们把每个点往外扩展一圈，则合法等价于对于每一对从同一个八联通块扩展来的点其均联通。

然后就完了。

注意特判几个边界情况。（$c=0$，$n=1$，$m=1$）

参考代码。