#P1094. 2023.03.19-第一题-米小游的RBG矩阵
-
1000ms
Tried: 832
Accepted: 253
Difficulty: 3
所属公司 :
米哈游
时间 :2023年3月19日
2023.03.19-第一题-米小游的RBG矩阵
题目思路
朴素的求连通块个数。两遍dfs,一次正常算,一次把B,G看作一样的字符算。做差即可。
代码
C++
#include<iostream>
using namespace std;
int n, m;
string s[1010];
bool vis1[1010][1010], vis2[1010][1010];
const int mv[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int dfs1(int x, int y) {
if(x < 0 || x >= n) return 0;
if(y < 0 || y >= m) return 0;
if(vis1[x][y]) return 0;
if(!vis1[x][y]) vis1[x][y] = true;
for(int i = 0; i < 4; i++) {
if(x + mv[i][0] < 0 || x + mv[i][0] >= n) continue;
if(y + mv[i][1] < 0 || y + mv[i][1] >= m) continue;
if(s[x + mv[i][0]][y + mv[i][1]] == s[x][y])
dfs1(x + mv[i][0], y + mv[i][1]);
}
return 1;
}
int dfs2(int x, int y) {
if(x < 0 || x >= n) return 0;
if(y < 0 || y >= m) return 0;
if(vis2[x][y]) return 0;
if(!vis2[x][y]) vis2[x][y] = true;
for(int i = 0; i < 4; i++) {
if(x + mv[i][0] < 0 || x + mv[i][0] >= n) continue;
if(y + mv[i][1] < 0 || y + mv[i][1] >= m) continue;
if(s[x][y] == 'G' || s[x][y] == 'B') {
if(s[x + mv[i][0]][y + mv[i][1]] == 'G' || s[x + mv[i][0]][y + mv[i][1]] == 'B')
dfs2(x + mv[i][0], y + mv[i][1]);
}
else if(s[x + mv[i][0]][y + mv[i][1]] == s[x][y])
dfs2(x + mv[i][0], y + mv[i][1]);
}
return 1;
}
int main() {
cin >> n >> m;
for(int i = 0; i < n; i++) {
cin >> s[i];
}
int cnt = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
cnt += dfs1(i, j);
}
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
cnt -= dfs2(i, j);
}
}
cout << cnt;
return 0;
}
Java
import java.util.*;
public class Main {
static final int N = 1010;
static char[][] g = new char[N][N];
static boolean[][] st = new boolean[N][N];
static int[] dx = {-1, 1, 0, 0}, dy = {0, 0, 1, -1};
static int n, m;
static int[] res = new int[2];
static void dfs(int x, int y, char c) {
st[x][y] = true;
for (int i = 0; i < 4; i++) {
int a = x + dx[i], b = y + dy[i];
if (a < 0 || a >= n || b < 0 || b >= m || st[a][b] || g[a][b] != c) continue;
dfs(a, b, c);
}
}
static void query(int u) {
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!st[i][j]) {
dfs(i, j, g[i][j]);
cnt++;
}
}
}
res[u]=cnt;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
for (int i = 0; i < n; i++) {
g[i] = sc.next().toCharArray();
}
query(0);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (g[i][j] == 'B') g[i][j] = 'G';
}
}
for (int i = 0; i < n; i++) Arrays.fill(st[i], false);
query(1);
System.out.println(res[0] - res[1]);
}
}
Python3(必须要使用pypy才可以ac)
import sys
sys.setrecursionlimit(1000000)
n, m = map(int, input().strip().split())
arr = [input().strip() for _ in range(n)]
visited1 = [[False] * m for _ in range(n)]
visited2 = [[False] * m for _ in range(n)]
def dfs(arr, visited1, i, j):
visited1[i][j] = True
direction = [[0, 1], [0, -1], [1, 0], [-1, 0]]
for x, y in direction:
si = i + x
sj = j + y
if si >= 0 and si < n and sj >= 0 and sj < m and not visited1[si][sj] and arr[i][j] == arr[si][sj]:
dfs(arr, visited1, si, sj)
def dfs2(arr, visited2, i, j):
visited2[i][j] = True
direction = [[0, 1], [0, -1], [1, 0], [-1, 0]]
for x, y in direction:
si = i + x
sj = j + y
if si >= 0 and si < n and sj >= 0 and sj < m and not visited2[si][sj]:
if arr[i][j] == 'G' or arr[i][j] == 'B':
if arr[si][sj] == 'G' or arr[si][sj] == 'B':
dfs2(arr,visited2, si, sj)
elif arr[i][j] == arr[si][sj]:
dfs2(arr, visited2, si, sj)
count = 0
for i in range(n):
for j in range(m):
if not visited1[i][j]:
dfs(arr, visited1, i, j)
count += 1
for i in range(n):
for j in range(m):
if not visited2[i][j]:
dfs2(arr, visited2, i, j)
count -= 1
print(count)
题目内容
米小游是一位蓝绿色盲,他面对许多日常生活中我们认为很容易的事情,都需要付出比常人更大的努力。
有一天,他收到了一个矩阵,矩阵的每个格子的颜色是红色、绿色和蓝色三种颜色之中的一个,但由于他无法分辨蓝色和绿色,因此在他眼里这个矩阵只有两种颜色。他想要对这个矩阵进行分析,但是由于他的视觉缺陷,他自己看到的连通块数量可能比实际的连通块数量少。
你可以帮米小游计算连通块少了多少吗?
注意: 题目中的连通是指上下左右的四连通。
输入描述
第一行输入两个正整数 n 和 m ,代表矩阵的行数和列数。
接下来的 n 行,每行输入一个长度为 m 的,仅包含 R 、G 、B 三种颜色的字符串,代表米小游拿到的矩阵。
1≤n,m≤1000
输出描述
一个整数,代表米小游视角里比真实情况少的连通块数量。
样例
输入
2 6
RRGGBB
RGBGRR
输出
3
样例解释
米小游视角里有 3 个连通块,而实际上有 6 个连通块,所以米小游视角的连通块数量比真实情况少了 3 个。