背景

  一位名叫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不大于初始状态下黑格子的数量。

来源

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