HDU1045FireNet(搜索/贪心/二分图最大匹配)

题目链接：点击打开链接

题意：类似于八皇后问题，每行每列不能产生冲突，但此题图中有墙，两个碉堡如果隔了墙是可以放到同一行/列的。

思路：

一：搜索，由于数据规模很小，搜索是最直接的方式

二：贪心，每个空地都有一个影响范围，一旦某块空地放置了碉堡，那么它的影响范围内所有空地都不能放碉堡了。贪心规则：每次选取影响范围最小的空地放置碉堡，然后就把这个空地影响范围内所有空地标记，按这种方法最后放置的碉堡数一定是最多的 。

三：二分图最大匹配，暂时略。

搜索：

// HDU 1045 Fire Net.cpp 0ms/1000ms
#include 
#include 
#include 
#include 
using namespace std;
int n, re, map[5][5], book[5][5];
int next[2][2] = { 0,-1,-1,0 };
int check(int row, int col) {
if (map[row][col] == 0) return 0;
for (int i = 0; i <2; i++) {
int x = row + ::next[i][0];
int y = col + ::next[i][1];
while (x >= 0 && y >= 0) {
if (map[x][y] == 0) break;//遇碉堡前遇墙，放到（row,col）对于此行/列满足，此行/列不用再判断
if (map[x][y] && book[x][y]) return 0; //遇墙前遇碉堡，不满足
x = x + ::next[i][0];
y = y + ::next[i][1];
}
}
return 1;
}
void dfs(int row, int col, int sum) {
if (row == n) {
re = max(re, sum);
return;
}
int y = (col + 1) % n;
int x = row + (y == 0);
dfs(x, y, sum);
if (check(row, col)) {
book[row][col] = 1;
dfs(x, y, sum + 1);
book[row][col] = 0;
}
}
int main(){
char s[10];
while (scanf("%d", &n) != EOF && n) {
re = 0;
memset(book, 0, sizeof(book));
for (int i = 0; i scanf("%s", s);
for (int j = 0; j map[i][j] = s[j] == '.' ? 1 : 0;
}
}
dfs(0, 0, 0);
printf("%d\n", re);
}
    return 0;
}

// HDU 1045 Fire Net（2）.cpp 0ms/1000ms
#include 
#include 
#include 
#include 
using namespace std;
int n, map[5][5], book[5][5];
int next[4][2] = { 0,-1,0,1,-1,0,1,0 };
struct node {
int x, y, num;
node(){}
node(int a,int b,int c):x(a),y(b),num(c){}
bool operator<(node &a) {
return this->num }
}a[20];
int cal(int x,int y) {//计算影响范围大小
int cnt = 0;
for (int i = 0; i <4; i++) {
int r = x + ::next[i][0];
int c = y + ::next[i][1];
while (r >= 0 && r = 0 && c if (map[r][c] == 0) break;
cnt++;
r = r + ::next[i][0];
c = c + ::next[i][1];
}
}
return cnt;
}
void deal(int x, int y) {//标记影响范围内的点
book[x][y] = 1;
for (int i = 0; i <4; i++) {
int r = x + ::next[i][0];
int c = y + ::next[i][1];
while (r >= 0 && r = 0 && c if (map[r][c] == 0) break;
book[r][c] = 1;
r = r + ::next[i][0];
c = c + ::next[i][1];
}
}
}
int main(){
int re;
char s[10];
while (scanf("%d", &n) != EOF && n) {
re = 0;
memset(book, 0, sizeof(book));
for (int i = 0; i scanf("%s", s);
for (int j = 0; j map[i][j] = s[j] == '.' ? 1 : 0;
}
}
for (int i = 0; i for (int j = 0; j int t = cal(i, j);
a[i * n + j] = node(i, j, t);
}
}
sort(a, a + n*n);
for (int i = 0; i int x = a[i].x, y = a[i].y;
if (map[x][y] == 0 || book[x][y] == 1) continue;
re++;
deal(x, y);
}
printf("%d\n", re);
}
    return 0;
}