Rooks
时间: 1ms 内存:128M
描述:
You have unexpectedly become the owner of a large chessboard, having fifteen squares to each side. Because you do not know how to play chess on such a large board, you find an alternative way to make use of it.
In chess, a rook attacks all squares that are in the same row or column of the chessboard as it is. For the purposes of this problem, we define a rook as also attacking the square on which it is already standing.
Given a set of chessboard squares, how many rooks are needed to attack all of them?
输入:
Input consists of a number of test cases. Each test case consists of fifteen lines each containing fifteen characters depicting the chess board. Each character is either a period (.) or a hash (#). Every chessboard square depicted by a hash must be attacked by a rook. After all the test cases, one more line of input appears. This line contains the word END.
输出:
Output consists of exactly one line for each test case. The line contains a single integer, the minimum number of rooks that must be placed on the chess board so that every square marked with a hash is attacked.
示例输入:
...............
...............
...............
...............
...............
...............
...............
.......#.......
...............
...............
...............
...............
...............
...............
...............
END
示例输出:
1
提示:
参考答案(内存最优[800]):
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
#define FR(i,a,b) for(int i=(a);i<(b);++i)
#define FOR(i,n) FR(i,0,n)
#define CLR(x,a) memset(x,a,sizeof(x))
#define setmax(a,b) a = max(a,b)
#define setmin(a,b) a = min(a,b)
typedef long long ll;
const int R=15,C=15;
int i;
char grid[16][16];
int colset[16];
void doit() {
FOR(r,R) {
scanf("%s",grid[r]);
if (0==strcmp("END",grid[r])) exit(0);
}
int ans = 15;
FOR(S,(1<<R)) {
CLR(colset,0);
FOR(r,R) if (0==((1<<r)&S)) {
FOR(c,C) if (grid[r][c]=='#') colset[c]=1;
}
int now = 0;
FOR(c,C) now += colset[c];
setmax(now, __builtin_popcount(S));
setmin(ans, now);
}
printf("%d\n",ans);
}
int main() {
while (1) doit();
}
参考答案(时间最优[20]):
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <string>
#include <vector>
using namespace std;
#define SZ(v) int((v).size())
#define FR(i,a,b) for(int i=(a);i<(b);++i)
#define FOR(i,n) FR(i,0,n)
#define FORI(i,v) FOR(i,SZ(v))
#define CLR(x,a) memset(x,a,sizeof(x))
#define setmax(a,b) a = max(a,b)
#define setmin(a,b) a = min(a,b)
typedef long long ll;
int R,C;
char buf[16];
int deg[16][16];
int nod[16][16][4];
const int MAXV = 514;
bool mark[MAXV];
int cap[MAXV][MAXV];
vector<int> edg[MAXV];
const int s=MAXV-2,t=MAXV-1;
void connect(int v, int w, int u) {
cap[v][w] = u;
cap[w][v] = 0;
edg[v].push_back(w);
edg[w].push_back(v);
}
int dr[] = { -1, 0, 1, 0 },
dc[] = { 0, 1, 0, -1 };
const int inf = 123456789;
int dfs(int v, int flocap=inf) {
if (v==t) return flocap;
if (mark[v]) return 0;
mark[v] = 1;
FORI(i,edg[v]) {
int w = edg[v][i];
if (cap[v][w]) {
int f = dfs(w, min(flocap, cap[v][w]));
if (f) {
cap[v][w] -= f;
cap[w][v] += f;
return f;
}
}
}
return 0;
}
void doit() {
scanf("%d%d",&R,&C);
if (R==0) exit(0);
FOR(v,MAXV) edg[v].clear();
CLR(cap,0);
FOR(r,R) {
FOR(c,C) {
scanf(" %s",buf);
if (0==strcmp("x",buf)) deg[r][c]=0;
else deg[r][c] = strlen(buf);
}
}
int next = 0;
FOR(r,R) FOR(c,C) {
if (deg[r][c] != 2) {
FOR(k,4) nod[r][c][k] = next;
if ((r+c)%2) connect(s, next, deg[r][c]);
else connect(next, t, deg[r][c]);
++next;
} else {
FOR(k,4) nod[r][c][k] = next + (k%2);
if ((r+c)%2) FOR(k,2) connect(s, next+k, 1);
else FOR(k,2) connect(next+k, t, 1);
next += 2;
}
}
FOR(r,R) FOR(c,C) if ((r+c)%2) {
FOR(k,4) {
int r2 = r+dr[k], c2 = c+dc[k];
if (r2<0||r2>=R||c2<0||c2>=C) continue;
int k2 = (k+2)%4;
connect(nod[r][c][k], nod[r2][c2][k2], 1);
}
}
while (1) {
CLR(mark,0);
int f = dfs(s);
if (f == 0) break;
}
int ed=0,od=0;
FOR(r,R) FOR(c,C) {
if ((r+c)%2) od += deg[r][c];
else ed += deg[r][c];
}
bool happy = 1;
FOR(v,MAXV) if (cap[s][v] || cap[v][t]) happy = 0;
printf("%s\n", happy ? "SOLVABLE" : "UNSOLVABLE");
}
int main() {
while (1) doit();
}
题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。