[UVA][匈牙利] 1514 - Piece it together
Tom has developed a special kind of puzzle: it involves a whole bunch of identical puzzle pieces. The pieces have the shape of three adjoint squares in an L-shape. The corner square is black, the two adjacent squares are white.
The puzzler is given a pattern of black and white squares in a rectangular grid. The challenge is to create that pattern using these pieces. The pieces can be rotated, but must not overlap.
Tom has already designed a few nice patterns, but he needs to find out if they can be constructed with the pieces at all. Rather than trying to test this for each pattern by hand, he wants to write a computer program to determine this for him. Can you help him?
Input
On the first line a positive integer: the number of test cases, at most 100. After that per test case:
- one line with two integers n and m
(1
n, m500):
the height and width of the grid containing the pattern, respectively.
- n lines, each containing m characters, denoting the grid. Each character is `B', `W', or `.', indicating a black, white or empty square respectively.
The grid contains at least one black or white square.
Output
Per test case:
- one line with either ``YES" or ``NO", indicating whether or not it is possible to construct the pattern with the puzzle pieces. You may assume that there is an infinite supply of pieces.
Sample Input
2 3 4 BWW. WWBW ..WB 3 3 W.. BW. WBW
Sample Output
YES NO
題目描述：
用上述 L 型拼圖進行完美覆蓋。可能輸出 "YES"，反之 "NO"。
題目解法：
自己常用的 maxflow 太慢，可能要換其他 maxflow 的演算法。
不過這題匈牙利算法在底線上通過了。
將每一個 B 拆成 2 個點，分別為水平跟垂直。
也就是說 B 只會從水平匹配到一個 W，垂直匹配到一個 W。
因此問題就是要詢問拆點後，能不能進行完美匹配。
非常底線的做法，接近 TLE orz
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
using namespace std;
struct Node {
int y;
int next;
} edge[1000005];
int e, head[250005];
void addEdge(int x, int y) {
edge[e].y = y;
edge[e].next = head[x], head[x] = e++;
}
int mx[250005], my[250005], used[250005];
int dfs(int now) {
int i, x;
for(i = head[now]; i != -1; i = edge[i].next) {
x = edge[i].y;
if(!used[x]) {
used[x] = 1;
if(my[x] == -1 || dfs(my[x])) {
mx[now] = x, my[x] = now;
return 1;
}
}
}
return 0;
}
int main() {
int testcase, n, m;
int i, j;
scanf("%d", &testcase);
char g[505][505];
int node[505][505];
while(testcase--) {
scanf("%d %d", &n, &m);
for(i = 0; i < n; i++)
scanf("%s", g[i]);
e = 0;
memset(head, -1, sizeof(head));
int B = 0, W = 0;
for(i = 0; i < n; i++) {
for(j = 0; j < m; j++) {
if(g[i][j] == 'W')
node[i][j] = W++;
if(g[i][j] == 'B')
node[i][j] = B++;
}
}
if(W != B*2) {
puts("NO");
continue;
}
int source = 0, sink = W + B*2 + 1;
for(i = 0; i < n; i++) {
for(j = 0; j < m; j++) {
if(g[i][j] == 'B') {
// horizontal
if(j-1 >= 0 && g[i][j-1] == 'W')
addEdge(node[i][j], node[i][j-1]);
if(j+1 < m && g[i][j+1] == 'W')
addEdge(node[i][j], node[i][j+1]);
// vertical
if(i-1 >= 0 && g[i-1][j] == 'W')
addEdge(node[i][j]+B, node[i-1][j]);
if(i+1 < n && g[i+1][j] == 'W')
addEdge(node[i][j]+B, node[i+1][j]);
}
}
}
memset(mx, -1, sizeof(mx));
memset(my, -1, sizeof(my));
int match = 0;
B = B*2;
for(i = 0; i < B; i++) {
if(mx[i] == -1) {
memset(used, 0, sizeof(used));
if(dfs(i))
match++;
else
break;// cut condition.
}
}
puts(match == B ? "YES" : "NO");
}
return 0;
}
Thank you..