?
Input Input will include several test cases. The first line of a test case contains two integers N and M, representing, respectively, the number of rows and columns of the land (1 <= N, M <= 100). The second line will contain an integer K indicating the number of squares that have been turned into ponds ( (N x M) - K <= 50). Each of the next K lines contains two integers X and Y describing the position of a square which was turned into a pond (1 <= X <= N and 1 <= Y <= M). The end of input is indicated by N = M = 0.?
Output For each test case in the input your program should first output one line, containing an integer p representing the maximum number of properties which can be sold. The next p lines specify each pair of squares which can be sold simultaneity. If there are more than one solution, anyone is acceptable. there is a blank line after each test case. See sample below for clarification of the output format.?
Sample Input4 4 6 1 1 1 4 2 2 4 1 4 2 4 4 4 3 4 4 2 3 2 2 2 3 1 0 0
?
Sample Output4 (1,2)--(1,3) (2,1)--(3,1) (2,3)--(3,3) (2,4)--(3,4) 3 (1,1)--(2,1) (1,2)--(1,3) (2,3)--(3,3)? ????????? 题目大意:给你一个矩形,然后输入矩形里面池塘的坐标(不能放东西的地方),问可以放的地方中,最多可以放多少块1*2的长方形方块,并输出那些方块的位置。 ??????????这道题感觉出得很好,平时经常会遇到这些问题,但是不知道怎么解决。这个问题就是二分匹配,用匈牙利算法可以搞定,问题就是如何建图,相邻连着的就可以加一条边。这样建图后,最大匹配就是最大值。坐标就是他的pre[]这样问题就解决了。 链接:http://acm.hdu.edu.cn/showproblem.php?pid=1507 代码:
#include <iostream> #include <stdio.h> #include <memory.h> using namespace std; const int N = 105; int pre[N*N], map[N*N]; bool flag[N*N], vis[N*N]; int n, m, total; int find(int cur) { int k; k = cur + 1; if(cur%m+1 < m && k < total && map[k] != -1 && !flag[k]) { flag[k] = true; if(pre[k] == -1 || find(pre[k])) { pre[k] = cur; return 1; } } k = cur + m; if(k < total && map[k] != -1 && !flag[k]) { flag[k] = true; if(pre[k] == -1 || find(pre[k])) { pre[k] = cur; return 1; } } k = cur - 1; if(cur%m > 0 && k >= 0 && map[k] != -1 && !flag[k]) { flag[k] = true; if(pre[k] == -1 || find(pre[k])) { pre[k] = cur; return 1; } } k = cur - m; if(k >= 0 && map[k] != -1 && !flag[k]) { flag[k] = true; if(pre[k] == -1 || find(pre[k])) { pre[k] = cur; return 1; } } return 0; } int main() { int i, k, t, x, y, sum; while(scanf("%d %d", &n, &m), n && m) { total = n * m; memset(vis, false, sizeof(vis)); memset(map, -1, sizeof(map)); memset(pre, -1, sizeof(pre)); for(i = 0; i < total; i++) { map[i] = i; } scanf("%d", &t); while(t--) { scanf("%d %d", &x, &y); k = (x-1)*m + (y-1); map[k] = -1; } sum = 0; for(i = 0; i < total; i++) { if(map[i] != -1) { memset(flag, false, sizeof(flag)); sum += find(map[i]); } } printf("%d\n", sum/2); for(i = 0; i < total; i++) { if(map[i] != -1 && pre[i] != -1 && !vis[pre[i]] && !vis[i]) { vis[pre[i]] = vis[i] = true; printf("(%d,%d)--(%d,%d)\n", i/m+1, i%m+1, pre[i]/m+1, pre[i]%m+1); } } printf("\n"); } return 0; }?