lanzerb 的部落在 A 国的上部,他们不满天寒地冻的环境,于是准备向 A 国的下部征战来获得更大的领土。 A 国是一个 M*N 的矩阵,其中某些地方是城镇,某些地方是高山深涧无人居住。lanzerb 把自己的部落分成若干支军队,他们约定: 1. 每支军队可以从任意一个城镇出发,并只能从上往向下征战,不能回头。途中只能经过城镇,不能经过高山深涧。 2. 如果某个城镇被某支军队到过,则其他军队不能再去那个城镇了。 3. 每支军队都可以在任意一个城镇停止征战。 4. 所有军队都很奇怪,他们走的方法有点像国际象棋中的马。不过马每次只能走 1*2 的路线,而他们只能走 R*C 的路线。 lanzerb 的野心使得他的目标是统一全国,但是兵力的限制使得他们在配备人手时力不从心。假设他们每支军队都能顺利占领这支军队经过的所有城镇,请你帮 lanzerb 算算至少要多少支军队才能完成统一全国的大业。
第一行包含 4 个整数 M、N、R、C,意义见问题描述。接下来 M 行每行一个长度为 N 的字符串。如果某个字符是'.',表示这个地方是城镇;如果这个字符时'x',表示这个地方是高山深涧。
输出一个整数,表示最少的军队个数。
又臭又长~
- 1#include 2#include 3#include 4 using namespace std;
- 5 const int maxn = 2610;
- 6 int G[maxn][maxn],
- y[maxn],
- num[maxn][maxn];
- 7 bool vis[maxn],
- f[maxn][maxn];
- 8 int dx[5],
- dy[5];
- 9 int n,
- m,
- r,
- c,
- id;
- 10 char s[501];
- 11 long long ans;
- 12 bool dfs(int u) {
- 13
- for (int i = 1; i <= id; i++) 14
- if (G[u][i] && !vis[i]) {
- 15 vis[i] = 1;
- 16
- if (!y[i] || dfs(y[i])) {
- 17 y[i] = u;
- 18
- return 1;
- 19
- }
- 20
- }
- 21
- return 0;
- 22
- }
- 23 int main() {
- 24 scanf("%d%d%d%d", &n, &m, &r, &c);
- 25 dx[0] = r;
- dx[1] = r;
- dx[2] = c;
- dx[3] = c;
- 26 dy[0] = c;
- dy[1] = -c;
- dy[2] = r;
- dy[3] = -r;
- 27
- for (int i = 1; i <= n; i++) {
- 28 scanf("%s", s);
- 29
- for (int j = 0; j) {
- 30
- if (s[j] == '.') f[i][j + 1] = 1,
- num[i][j + 1] = ++id;
- 31
- }
- 32
- }
- 33
- for (int i = 1; i <= n; i++) 34
- for (int j = 1; j <= m; j++) 35
- if (f[i][j]) for (int k = 0; k < 4; k++) {
- 36 int x = i + dx[k],
- y = j + dy[k];
- 37
- if (x < 1 || x > n || y < 1 || y > m) continue;
- 38
- if (f[x][y]) G[num[i][j]][num[x][y]] = 1;
- 39
- }
- 40
- for (int i = 1; i <= id; i++) {
- 41 memset(vis, 0, sizeof(vis));
- 42
- if (dfs(i)) ans++;
- 43
- }
- 44 printf("%d\n", id - ans);
- 45
- }
来源: http://www.bubuko.com/infodetail-1959118.html