为了信仰 Beta Round ＃1 (新疆省队互测Week1-Day1)

背景

　　一位名叫tangjz的OIer探险家却无意中得到了正义力量，从此决定改变世界。

　　tangjz来到了原来的OI村，此时的OI村已经四分五裂，不复昔日繁荣的景象。

　　萌化的tangjz拥有了修补大地的力量，他决定为了这些有着信仰的OIer们，使得这些OIer们能重聚。

描述

　　现在的OI村在tangjz的探测器上是一幅N*M的网格图，行和列的标号都是从0开始的，其中有一些地方是黑色的，表示此处土地在海平面之上(OIer只能在这种土地上)，还有一些地方是白色的，表示此处土地在海平面之下，创造一块土地(即将一个白格子变成黑色的)的代价是1。

　　其中有K块黑色格子上有幸存的OIer群。

　　由于tangjz想要节省力量去修复更多不和谐的事物，所以他要用最少的代价将这个K个OIer群连通。(这里的连通是指四联通，即上下左右连通)

输入格式

　　第一行两个正整数N和M，表示tangjz的探测范围。

　　接下来N行，每行一个长度为M的01串，即探测图。(其中0表示白色，1表示黑色)

　　第N+2行一个正整数K，表示有OIer群的个数。

　　接下来K行，每行两个非负整数Xi和Yi，表示第i个OIer群在探测器上的坐标。

输出格式

　　一个正整数Ans，表示最小代价。

样例输入

5 5
10101
01010
10101
01010
10101
2
0 0
4 4

样例输出

4

数据范围与约定

  • 对于20%的数据:N*M\leq 100
  • 存在20%的数据:K = 2
  • 对于68%的数据:N*M\leq 500
  • 对于100%的数据:min(N,M)\leq 9,max(N,M)\leq 100 ，K不大于初始状态下黑格子的数量。

来源

　　一看就是一眼题的对吧！不用是原题的对吧！