2015 百度之星 1003 棋盤占領 dfs

棋盤占領

Time Limit: 20 Sec  Memory Limit: 256 MB

http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=601&pid=1003

百小度最近迷戀上了一款遊戲，遊戲裡有一個n*m的棋盤，每個方格代表一個城池。
一開始的時候我們有g支軍隊，駐紮并占領了其中某些城池。然後我們可以在這些被占領城池的基礎上，吞并占領周圍的城池。


而其吞并占領的規則是這樣的——一旦一個城池A相鄰的上下左右四個城池中至少存在兩個被占領，且這兩個被占領的城池有公共點，那麼城池A也将被占領。
比如我們用1表示初始的占領狀态，0表示初始的未占領狀态。
那麼——


會最終會變成



而101則保持為101不變

現在告訴你一張地圖一開始所有被占領城池的資訊，問你最後多少個城池會被我們占領。

Input

第一行為T，表示輸入資料組數。

下面T組資料，對于每組資料，
第一行是兩個數n,m(1≤n,m≤500)，表示國土的大小為n*m。


第二行是一個整數g(1≤g≤1000)，表示我們一開始占領的城池數。
然後跟随g行，第i行一對整數x,y(1≤x≤n,1≤y≤m)，表示占領的第i個城池的坐标。

Output

對第i組資料，輸出

Case #i:

然後輸出一行，僅包含一個整數，表示最終有多少個城池被占領。

Sample Input

題意

題解：

直接暴力修改就好，這份代碼是kuangbin的，我看不了我的代碼 = =

我是dfs修改的，和某次cf的題很類似

代碼：