46分dfs求大佬看看
  • 板块P1331 海战
  • 楼主mayuhao666
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/9 14:43
  • 上次更新2024/8/9 15:37:12
查看原帖
46分dfs求大佬看看
1110408
mayuhao666楼主2024/8/9 14:43
#include <bits/stdc++.h>
using namespace std;
int n, m;
char a[1000][1000];

int fx[5] = {0, -1, +1, 0, 0};
int fy[5] = {0, 0, 0, -1, 1};
int dfs(int x, int y) {
	a[x][y] = '$';
	for (int i = 1; i <= 4; i++) {
		if (x + fx[i] > 0 && x + fx[i] <= n && y + fy[i] > 0 && y + fy[i] <= m && a[x + fx[i]][y + fy[i]] == '#')
			dfs(x + fx[i], y + fy[i]);
	}
}
bool d(int i, int j) {
	int c = 0;
	if (a[i][j] == '#')
		c++;
	if (a[i + 1][j] == '#')
		c++;
	if (a[i][j + 1] == '#')
		c++;
	if (a[i + 1][j + 1] == '#')
		c++;
	if (c == 3)
		return 0;
	return 1;
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
		}
	}
	int s = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (d(i, j) == 0) {
				cout << "Bad placement.";
				return 0;
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (a[i][j] == '#') {
				s++;
				dfs(i, j);
			}
		}
	}
	cout << "There are " << s << " ships.";
	return 0;
}
2024/8/9 14:43
加载中...