红与黑50分求调

鲁子欣 · 2024 年7 月 30 日 08:51

3. 红与黑

题目ID：8120必做题100分

题目描述

这间长方形客房铺有方形瓷砖。每个瓷砖都是红色或黑色。一个男人站在黑色的瓷砖上。从瓷砖中，他可以移动到四个相邻瓷砖中的一个。但他不能在红瓦上移动，他只能在黑色瓷砖上移动。

输入格式

输入由多个数据集组成。数据集以包含两个正整数W和H的行开始; W和H分别是x和y方向上的瓦片数量。W和H不超过20.数据集中还有H行，每行包含W个字符。每个字符代表一个图块的颜色，如下所示。’ . ’ - 黑色瓷砖’＃’ - 红色瓷砖’@’ - 黑色瓷砖上的男人（在数据集中只显示一次）当遇到W和H为0的时候，代表输入数据结束。

输出格式

对于每个数据集，您的程序应输出一行，其中包含他可以从初始图块（包括其自身）到达的图块数量。

样例

Input 1

7 7 …#.#… …#.#… ###.### …@… ###.### …#.#… …#.#… 0 0

Output 1

13

Input 2

1 1 @ 4 2 @### …# 0 0

Output 2

1 4

样例解释

他可以从初始图块（包括其自身）到达的图块数量为13。

数据范围

W和H分别是x和y方向上的瓦片数量。W和H不超过20.

#include <bits/stdc++.h>
using namespace std;
int n, m;
char a[105][105];
bool vis[105][105] = {};
int dx[8]{ 0,1,0,-1,-1,1,1,-1 };
int dy[8]{ -1,0,1,0,-1,1,-1,1 };
int sum = 0;
int xx, yy;
void dfs(int x, int y) {
    for (int i = 0; i < 4; i++) {
        int xx = x + dx[i];
        int yy = y + dy[i];//记录新位置
        if (vis[xx][yy] == 0 && xx >= 1 && yy >= 1 && xx <= m && yy <= n && a[xx][yy] != '#') {
            vis[xx][yy] = 1;
            sum++;
            dfs(xx, yy);
        }
    }
}
int main() {
	while (cin >> m >> n) {
		if (n == 0 && m == 0) {
			break;
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				cin >> a[i][j];
			}
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if (a[i][j] == '@') {
					dfs(i, j);
					break;
				}
			}
		}
		cout << sum << endl;
		sum = 0;
		vis[105][105]={};
	}
    return 0;
}

鲁子欣 · 2024 年7 月 30 日 08:55

有大佬吗

周子寓 · 2024 年7 月 30 日 08:58

不就是找联通块大小吗？

鲁子欣 · 2024 年7 月 30 日 08:58

YES

周子寓 · 2024 年7 月 30 日 08:59

你跑dfs，到一块就ans++,最后cout<<ans

鲁子欣 · 2024 年7 月 30 日 09:58

？？？
不懂

周子寓 · 2024 年7 月 30 日 10:49

@鲁子欣我知道你哪错了，dfs里n,m反了

鲁子欣 · 2024 年7 月 30 日 10:53

#include <bits/stdc++.h>
using namespace std;
int n, m;
char a[105][105];
bool vis[105][105] = {};
int dx[8]{ 0,1,0,-1,-1,1,1,-1 };
int dy[8]{ -1,0,1,0,-1,1,-1,1 };
int sum = 0;
int xx, yy;
void dfs(int x, int y) {
    for (int i = 0; i < 4; i++) {
        int xx = x + dx[i];
        int yy = y + dy[i];//记录新位置
        if (vis[xx][yy] == 0 && xx >= 1 && yy >= 1 && xx <= n && yy <= m && a[xx][yy] != '#') {
            vis[xx][yy] = 1;
            sum++;
            dfs(xx, yy);
        }
    }
}
int main() {
	while (cin >> m >> n) {
		if (n == 0 && m == 0) {
			break;
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				cin >> a[i][j];
			}
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if (a[i][j] == '@') {
					dfs(i, j);
					break;
				}
			}
		}
		cout << sum << endl;
	}
    return 0;
}

周子寓 · 2024 年7 月 30 日 10:57

萌新:

#include <bits/stdc++.h>
using namespace std;
int n, m;
char a[105][105];
bool vis[105][105] = {};
int dx[8]{ 0,1,0,-1,-1,1,1,-1 };
int dy[8]{ -1,0,1,0,-1,1,-1,1 };
int sum = 0;
int xx, yy;
void dfs(int x, int y) {
	for (int i = 0; i < 4; i++) {
		int xx = x + dx[i];
		int yy = y + dy[i];//记录新位置
		if (vis[xx][yy] == 0 && xx >= 1 && yy >= 1 && xx <= n && yy <= m && a[xx][yy] != '#') {
			vis[xx][yy] = 1;
			sum++;
			dfs(xx, yy);
		}
	}
}
int main() {
	while (cin >> m >> n) {
		if (n == 0 && m == 0) {
			break;
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				cin >> a[i][j];
			}
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if (a[i][j] == '@') {
					dfs(i, j);
					break;
				}
			}
		}
		if (sum == 0) {
			cout << 1;
		}
		else {
			cout << sum << endl;
		};
	}
	return 0;
}

为什么我改了之后A了？

周子寓 · 2024 年7 月 30 日 11:02

萌新:

#include <bits/stdc++.h>
using namespace std;
int n, m;
char a[105][105];
bool vis[105][105] = {};
int dx[8]{ 0,1,0,-1,-1,1,1,-1 };
int dy[8]{ -1,0,1,0,-1,1,-1,1 };
int sum = 0;
int xx, yy;
void dfs(int x, int y) {
    for (int i = 0; i < 4; i++) {
        int xx = x + dx[i];
        int yy = y + dy[i];//记录新位置
        if (vis[xx][yy] == 0 && xx >= 1 && yy >= 1 && xx <= m && yy <= n && a[xx][yy] != '#') {
            vis[xx][yy] = 1;
            sum++;
            dfs(xx, yy);
        }
    }
}
int main() {
	while (cin >> m >> n) {
		if (n == 0 && m == 0) {
			break;
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				cin >> a[i][j];
			}
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if (a[i][j] == '@') {
					dfs(i, j);
					break;
				}
			}
		}
		cout << sum << endl;
		sum = 0;
		vis[105][105]={};
	}
    return 0;
}

从这个代码开始改，把vis[105][105]={};改成memset(vis,0,sizeof vis);,把if (vis[xx][yy] == 0 && xx >= 1 && yy >= 1 && xx <= m && yy <= n && a[xx][yy] != '#') {改成if (vis[xx][yy] == 0 && xx >= 1 && yy >= 1 && xx <= n && yy <= m && a[xx][yy] != '#') {

周子寓 · 2024 年7 月 30 日 11:03

解决方案

鲁子欣 · 2024 年7 月 30 日 11:05

萌新:

#include <bits/stdc++.h>
using namespace std;
int n, m;
char a[105][105];
bool vis[105][105] = {};
int dx[8]{ 0,1,0,-1,-1,1,1,-1 };
int dy[8]{ -1,0,1,0,-1,1,-1,1 };
int sum = 0;
int xx, yy;
void dfs(int x, int y) {
    for (int i = 0; i < 4; i++) {
        int xx = x + dx[i];
        int yy = y + dy[i];//记录新位置
        if (vis[xx][yy] == 0 && xx >= 1 && yy >= 1 && xx <= m && yy <= n && a[xx][yy] != '#') {
            vis[xx][yy] = 1;
            sum++;
            dfs(xx, yy);
        }
    }
}
int main() {
	while (cin >> m >> n) {
		if (n == 0 && m == 0) {
			break;
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				cin >> a[i][j];
			}
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if (a[i][j] == '@') {
					dfs(i, j);
					break;
				}
			}
		}
		cout << sum << endl;
		sum = 0;
		vis[105][105]={};
	}
    return 0;
}

谢谢