avatar
fireworks99
keep hungry keep foolish

HDU 1045 Fire Net(DFS or bipartite graph match)

Description

给出一个地图,有空地,有墙,在空地上安排炮台,炮台会向四方攻击,但不会穿透墙壁,要避免炮台彼此攻击到,求最多能安排多少炮台?

Analyze

可以简单のDFS

另外的二分图匹配:

假设没有墙壁,为每行、每列标号,针对每个点进行建边,求最大匹配

1 1 1 1
2 2 2 2
3 3 3 3
4 4 4 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4

建边add(1, 1)add(1, 2)add(1, 3)add(1,4)add(2,1)……

在求最大匹配时,假设第一个表中的2匹配了第二个表中的3,那么相当于在第二行第三列建一座炮台,由于本行都是2,且2已经被分配,所以本行不会再被分配炮台;同理,本列都是3,且3已经被分配,所以本列不会再被分配炮台。如此限制了同行或同列不会出现两座炮台。

现在有墙,标号便可增加了,比如样例

4 .X.. .... XX.. ....
  • 1
  • 2
  • 3
  • 4
  • 5
1 X 2 2
3 3 3 3
X X 4 4
5 5 5 5
1 X 5 6
1 3 5 6
X X 5 6
2 4 5 6

Code

#include <cstdio> #include <cstring> #include <iostream> using namespace std; const int N = 205; char s[N][N]; int n, mat[N], idr, idc, gr[N][N], gc[N][N]; bool vis[N], g[N][N]; bool dfs(int u) { for (int v = 1; v <= idc; v++) { if (vis[v] || !g[u][v]) continue; vis[v] = 1; if (!mat[v] || dfs(mat[v])) { mat[v] = u; return 1; } } return 0; } int main() { while (scanf("%d", &n), n) { memset(g, false, sizeof(g)); memset(gr, 0, sizeof(gr)); memset(gc, 0, sizeof(gc)); memset(mat, 0, sizeof(g)); for (int i = 0; i < n; i++) scanf("%s", s[i]); idr = 0; for (int i = 0; i < n; i++) { idr++; for (int j = 0; j < n; j++) { if (s[i][j] == 'X') { if (j != 0 && j != n - 1) idr++; continue; } gr[i][j] = idr; } } idc = 0; for (int j = 0; j < n; j++) { idc++; for (int i = 0; i < n; i++) { if (s[i][j] == 'X') { if (i != 0 && i != n - 1) idc++; continue; } gc[i][j] = idc; } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (s[i][j] == 'X') continue; int u = gr[i][j], v = gc[i][j]; g[u][v] = true; } } int ans = 0; for (int i = 1; i <= idr; i++) { memset(vis, false, sizeof(vis)); if (dfs(i)) ans++; } printf("%d\n", ans); } return 0; }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89

Code of DFS

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int n, ans; char mp[10][10]; bool check(int x, int y) { if(mp[x][y] != '.') return 0; for(int i = y - 1; i >= 0; --i) if(mp[x][i] == 'B') return 0; else if(mp[x][i] == 'X') break; for(int i = x - 1; i >= 0; --i) if(mp[i][y] == 'B') return 0; else if(mp[i][y] == 'X') break; return 1; } void DFS(int pos, int num) { if(pos == n * n) { ans = max(ans, num); return ; } int x = pos / n, y = pos % n; if(check(x, y)) { mp[x][y] = 'B'; DFS(pos + 1, num + 1); mp[x][y] = '.'; } DFS(pos + 1, num); return ; } int main() { while(~scanf("%d", &n) && n) { for(int i = 0; i < n; ++i) scanf("%s", mp[i]); ans = 0; DFS(0, 0); cout << ans << '\n'; } return 0; }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
Site by Baole Zhao | Powered by Hexo | theme PreciousJoy