Je vais faire E --Bomber que je n'ai pas pu résoudre hier dans ABC.
E - Bomber Garder la grille dans un tableau bidimensionnel est fastidieux et prend du temps, alors gérez le nombre de bombes sur chacun des axes $ H et W $. Si vous sélectionnez le nombre maximum de chaque bombe sur les axes $ H et W $ et renvoyez la somme des valeurs maximales, la réponse semble correcte, mais cela ne suffit pas. En effet, il n'est pas possible de traiter le cas où il y a une bombe à l'intersection. S'il y a des bombes aux intersections, la somme de leurs maximums est -1.
Maintenez les points d'intersection en mettant un tuple dans le dict. 0 est le point où il n'y a pas de bombe, 1 est le point où il y a une bombe.
from collections import defaultdict
h, w, m = map(int, input().split())
cnt_h = [0] * h
cnt_w = [0] * w
dic = defaultdict(int)
for _ in range(m):
h_m, w_m = map(int, input().split())
cnt_h[h_m - 1] += 1
cnt_w[w_m - 1] += 1
dic[(h_m - 1, w_m - 1)] += 1
max_h = max(cnt_h)
max_w = max(cnt_w)
mh = []
mw = []
for i in range(h):
if max_h == cnt_h[i]:
mh.append(i)
for i in range(w):
if max_w == cnt_w[i]:
mw.append(i)
flag = False
for i in mh:
for j in mw:
if dic[(i, j)] == 0:
flag = True #S'il y a un point de 0, ce sera la valeur maximale, alors cassez-la.
break
if flag:
break
if flag:
print(max_h + max_w)
else:
print(max_h + max_w - 1)
Recommended Posts