Oil Skimming
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)
Problem Description
Thanks to a certain “green” resources company, there is a new profitable industry of oil skimming. There are large slicks of crude oil floating in the Gulf of Mexico just waiting to be scooped up by enterprising oil barons. One such oil baron has a special plane that can skim the surface of the water collecting oil on the water’s surface. However, each scoop covers a 10m by 20m rectangle (going either east/west or north/south). It also requires that the rectangle be completely covered in oil, otherwise the product is contaminated by pure ocean water and thus unprofitable! Given a map of an oil slick, the oil baron would like you to compute the maximum number of scoops that may be extracted. The map is an NxN grid where each cell represents a 10m square of water, and each cell is marked as either being covered in oil or pure water.
Input
The input starts with an integer K (1 <= K <= 100) indicating the number of cases. Each case starts with an integer N (1 <= N <= 600) indicating the size of the square grid. Each of the following N lines contains N characters that represent the cells of a row in the grid. A character of ‘#’ represents an oily cell, and a character of ‘.’ represents a pure water cell.
Output
For each case, one line should be produced, formatted exactly as follows: “Case X: M” where X is the case number (starting from 1) and M is the maximum number of scoops of oil that may be extracted.
Sample Input
1 6
……
.##…
.##…
….#.
….##
……
Sample Output
Case 1: 3
解題心得：
- 題意很簡單，就是要你在圖中去截取1x2的方塊，問最多能截取多少個。
- 就是一個二分匹配問題，還是很簡單的，有兩種建圖的方法
- 第一種是給每一個坐標編號，查找每一個‘#’的四周圖形，然后建一個雙向的圖，得到的答案除2就可以了。
- 第二種就更高級了，仔細觀察可以觀看一個點的行列之和與他四周的四個格子的行列和奇偶性一定是不同的，這樣就可以參考國際象棋的棋盤，黑色的方格匹配白色方格，二分匹配。
弱智建圖寫代碼：
#include<bits/stdc++.h>
using namespace std;
const int maxn = 610;
char maps[maxn][maxn];
bool vis[maxn*maxn];
vector <int> ve[maxn*maxn];
int n,dir[4][2] = {0,1,0,-1,-1,0,1,0},match[maxn*maxn];void init()
{scanf("%d",&n);for(int i=0;i<maxn;i++)ve[i].clear();memset(vis,0,sizeof(vis));memset(maps,0,sizeof(maps));memset(match,-1,sizeof(match));for(int i=1;i<=n;i++)scanf("%s",maps[i]+1);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(maps[i][j] == '#')for(int k=0;k<4;k++){int x = i + dir[k][0];int y = j + dir[k][1];if(maps[x][y] == '#')ve[i*n+j].push_back(x*n+y);//如果四周是‘#’就建立聯系}}bool dfs(int x)//match
{for(int i=0;i<ve[x].size();i++){int v = ve[x][i];if(!vis[v]){vis[v] = true;if(match[v] == -1 || dfs(match[v])){match[v] = x;return true;}}}return false;
}int solve()
{int ans = 0;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(maps[i][j] == '#'){memset(vis,0,sizeof(vis));if(dfs(i*n+j))ans++;}return ans;
}int main()
{int t;scanf("%d",&t);int cas = 1;while(t--){init();int ans = solve();printf("Case %d: %d\n",cas++,ans/2);//因為建立的是雙向圖，所以一定要除2}return 0;
}
)
