【題目敘述】https://zerojudge.tw/ShowProblem?problemid=d365
【解題想法】BFS
- a[i][j]:紀錄座標 (i, j) 的語言,此外,當這個點被拜訪過後,將其值改為 ‘0’。
#include <iostream>
#include <queue>
using namespace std;
#define pii pair<int,int>
#define F first
#define S second
const int maxn = 500;
char a[maxn][maxn];
int H, W, remain;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int cnt[26];
void bfs(int x, int y){
queue <pii> q;
q.push({x, y});
char target = a[x][y];
a[x][y] = '0';
while (!q.empty()){
pii now = q.front();
q.pop();
x = now.F;
y = now.S;
for (int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < H && ny >= 0 && ny < W && a[nx][ny] == target){
q.push({nx, ny});
a[nx][ny] = '0';
}
}
}
cnt[target - 'a']++;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int T;
string s;
cin >> T;
for (int Case = 1; Case <= T; Case++){
cin >> H >> W;
for (int i = 0; i < H; i++){
cin >> s;
for (int j = 0; j < W; j++){
a[i][j] = s[j];
}
}
for (int i = 0; i < 26; i++) cnt[i] = 0;
while (1){
int x = 0, y = 0;
bool flag = false;
for (int i = 0; i < H; i++){
for (int j = 0; j < W; j++){
if (a[i][j] != '0'){
x = i;
y = j;
flag = true;
break;
}
}
if (flag) break;
}
if (flag) bfs(x, y);
else break;
}
int mx = 0;
for (int i = 0; i < 26; i++){
mx = max(mx, cnt[i]);
}
cout << "World #" << Case << "\n";
while (mx){
for (int i = 0; i < 26; i++){
if (cnt[i] == mx){
cout << (char)('a'+i) << ": " << cnt[i] << "\n";
}
}
mx--;
}
}
return 0;
}
Python code (credit: Amy Chou)
執行結果:TLE
def bfs(x, y):
q = [(x, y)]
target = a[x][y]
a[x][y] = '0'
while q:
x, y = q.pop(0)
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx >= 0 and nx < H and ny >= 0 and ny < W and a[nx][ny] == target:
q.append((nx, ny))
a[nx][ny] = '0'
cnt[ord(target) - 97] += 1
#=== main ===
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
T = int(input())
for Case in range(1, T+1):
H, W = map(int, input().split())
a = []
for i in range(H):
a.append(list(input()))
cnt = [0 for _ in range(26)]
while True:
x = 0
y = 0
flag = False
for i in range(H):
for j in range(W):
if a[i][j] != '0':
x = i
y = j
flag = True
break
if flag:
break
if flag:
bfs(x, y)
else:
break
mx = 0
for i in range(26):
if cnt[i] > mx:
mx = cnt[i]
print(f"World #{Case}")
while mx:
for i in range(26):
if cnt[i] == mx:
print(f"{chr(i+97)}: {cnt[i]}")
mx -= 1