屎山bfs40分求调
查看原帖
屎山bfs40分求调
1271613
A_W_Lee楼主2024/10/21 13:03

上代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 105;
int mp[MAXN][MAXN], cnt = 0, sum, n, m;
bool mpf[MAXN][MAXN];

void bfs(int x, int y) {
	mpf[x][y] = 1, cnt++;

	if (x != 1) {
		if (y != 1) {
			if (mp[x - 1][y - 1] != -1 && !mpf[x - 1][y - 1])
				bfs(x - 1, y - 1);
			else if (mp[x - 1][y - 1] == -1)
				mp[x][y]++;
		}

		if (y != n) {
			if (mp[x - 1][y + 1] != -1 && !mpf[x - 1][y + 1])
				bfs(x - 1, y + 1);
			else if (mp[x - 1][y + 1] == -1)
				mp[x][y]++;
		}

		if (mp[x - 1][y] != -1 && !mpf[x - 1][y])
			bfs(x - 1, y);
		else if (mp[x - 1][y] == -1)
			mp[x][y]++;
	}

	if (x != m) {
		if (y != 1) {
			if (mp[x + 1][y - 1] != -1 && !mpf[x + 1][y - 1])
				bfs(x + 1, y - 1);
			else if (mp[x + 1][y - 1] == -1)
				mp[x][y]++;
		}

		if (y != n) {
			if (mp[x + 1][y + 1] != -1 && !mpf[x + 1][y + 1])
				bfs(x + 1, y + 1);
			else if (mp[x + 1][y + 1] == -1)
				mp[x][y]++;
		}

		if (mp[x + 1][y] != -1 && !mpf[x + 1][y])
			bfs(x + 1, y);
		else if (mp[x + 1][y] == -1)
			mp[x][y]++;
	}

	if (y != 1) {
		if (mp[x][y - 1] != -1 && !mpf[x][y - 1])
			bfs(x, y - 1);
		else if (mp[x][y - 1] == -1)
			mp[x][y]++;
	}

	if (y != n) {
		if (mp[x][y + 1] != -1 && !mpf[x][y + 1])
			bfs(x, y + 1);
		else if (mp[x][y + 1] == -1)
			mp[x][y]++;
	}

	if (cnt == sum)
		return ;
}

signed main() {
	int  i_id, j_id, mines = 0;
	char c;
	cin >> n >> m;

	for (int i = 1; i <= n; i++) {

		for (int j = 1; j <= m; j++) {

			cin >> c;

			if (c == '*')
				mp[i][j] = -1, mines++;
		}
	}

	sum = n * m - mines;
	bool f = 0;

	for (int i = 1; i <= n; i++) {

		for (int j = 1; j <= m; j++) {

			if (mp[i][j] == 0) {
				i_id = i, j_id = j, f = 1;
				break;
			}
		}

		if (f)
			break;
	}

	bfs(i_id, j_id);

	for (int i = 1; i <= n; i++) {

		for (int j = 1; j <= m; j++) {

			if (mp[i][j] == -1)
				cout << '*';
			else
				cout << mp[i][j];
		}

		cout << '\n';
	}


	return 0;
}

救救孩子!!

2024/10/21 13:03
加载中...