TÔ MÀU BẢN ĐỒ
Xem dạng PDF
Gửi bài giải
Điểm:
100,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
512M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C++, Pascal, Python, Scratch
Bình luận
print()
chỉ cần print()
100% dung ac full
i can thi lay code pascla nho (pascal): uses math; const dx: array[1..4] of integer = (0, 0, 1, -1); dy: array[1..4] of integer = (1, -1, 0, 0); var m, n, c: integer; a, mau: array[0..1005, 0..1005] of integer; i, j, k, q: integer; u, v, mauhangxom: array[1..4] of boolean;
procedure tomau(x, y: integer); var k, nx, ny: integer; begin fillchar(mauhangxom, sizeof(mauhangxom), false); for k := 1 to 4 do begin nx := x + dx[k]; ny := y + dy[k]; if (nx >= 1) and (nx <= m) and (ny >= 1) and (ny <= n) then if (a[nx, ny] <> a[x, y]) and (mau[nx, ny] > 0) then mauhang_xom[mau[nx, ny]] := true; end;
end;
begin readln(m, n, c); for i := 1 to m do for j := 1 to n do read(a[i, j]);
end.
scratch: (bỏ trống) python: #
đây là code gần đúng
from sys import stdin, setrecursionlimit from collections import defaultdict
setrecursionlimit(1000000)
Đọc input
def input(): return stdin.readline()
DSU (Disjoint Set Union - Union Find)
class DSU: def init(self, size): self.parent = list(range(size))
Đọc kích thước lưới và số màu
m, n, c = map(int, input().split()) grid = [list(map(int, input().split())) for _ in range(m)]
Gán chỉ số duy nhất cho mỗi ô (flatten 2D -> 1D)
def index(x, y): return x * n + y
dsu = DSU(m * n)
Bước 1: Gom vùng liên thông (giá trị giống nhau, kề nhau)
for i in range(m): for j in range(n): for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]: ni, nj = i + dx, j + dy if 0 <= ni < m and 0 <= nj < n and grid[i][j] == grid[ni][nj]: dsu.union(index(i, j), index(ni, nj))
Đánh ID vùng
regionmap = {} regionid = 0 celltoregion = [[-1]*n for _ in range(m)]
for i in range(m): for j in range(n): rep = dsu.find(index(i, j)) if rep not in regionmap: regionmap[rep] = regionid regionid += 1 celltoregion[i][j] = region_map[rep]
Bước 2: Xây đồ thị vùng kề nhau khác giá trị
adj = defaultdict(set) for i in range(m): for j in range(n): r1 = celltoregion[i][j] for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]: ni, nj = i + dx, j + dy if 0 <= ni < m and 0 <= nj < n: r2 = celltoregion[ni][nj] if r1 != r2: adj[r1].add(r2)
Bước 3: Tô màu Greedy các vùng
regioncolor = {} for u in range(regionid): used = {regioncolor[v] for v in adj[u] if v in regioncolor} for color in range(1, c + 1): if color not in used: region_color[u] = color break
In kết quả
print(max(regioncolor.values())) for i in range(m): print(' '.join(str(regioncolor[celltoregion[i][j]]) for j in range(n)))
bây ơi , đến giờ bài hết lỗi r...
nhập 1 thứ có trong python là đc :) ví dụ input print hoặc ... :)
tớ ko làm đc
? là ra
Chỉ cần
...là xong.... là code ?🤔😏
pass hoac print()
code cho ai can diem : print()
hoặc #
siu làm bậy cũng ra dduowcj100 điểm
Code C++: cout<< 0;
Ko thể tin đc. Lỗi nặng luôn
python code:
passCode Pascal: begin writeln() end.
Ko cần print nó cũng đúng ảo thật đếy:)
Ủa tôi làm tùm lum cũng 100% đúng
random ra cái bài này
mấy bài liên quan đến hình mà đề lại không cho hình
bài này bị lỗi r
siu,làm bậy cũng đúng
Ừ, tôi cũng vậy á
ko tin , show code rồi mới tin , tôi vode bạn
BÀI NÓ CỨ QUÁ THỜI GIAN
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
khi bấm vào lá cờ xanh nói ( )
print(89) là 100% điểm
🤔?
cần gì,gõ print() là AC
chỉ cần #
0 là được
ảo thế
WWWHHHAAATTTTT HOW
print(n) (với n là số bất kì) cx đúng nha
hoặc chỉ cần #
invalid return hết, sai bét
import
sai rồi
.