được bạn share cho cái bài tập
giống như game kim cương khi mà hàng ngang hàng dọc hoặc hàng chéo có 4+ viên đá cùng màu thì nó sẽ biến mất, mấy viên đá ở trên sẽ rơi xuống thế chỗ viên đá biến mất.
mỗi lần input thì có 1 viên đá rơi xuống bàn.
đề bài là từ 1 đống input cho ra output là hình dạng cuối của bàn chơi.
đề bài tiếng đức cho bạn nào muốn google translate
In dieser Aufgabe sollen Sie den Kern einer Computerspiel-Engine schreiben. Die Spiel-Mechanik
kann man sich als eine Mischung aus „Vier gewinnt“ und „Candy Crush“ vorstellen: Auf ein
diskretes Spielfeld Z × N0 fallen von oben (aus positiver y-Richtung) nacheinander einzelne
Spielsteine (nachfolgend „Steine“) unterschiedlicher Farben herunter und bilden Stapel. Sobald
vier oder mehr Steine der selben Farbe vertikal, horizontal oder diagonal in einer geraden Linie zusammenhängen, lösen diese sich auf; die darüber liegenden Steine rutschen dann nach
unten nach. Auch wenn ein Stein Teil zweier Viererlinien ist, lösen sich beide auf (z. B. wenn
sieben Steine T-förmig angeordnet sind oder sich zwei Linien in anderer Weise überschneiden).
Die Schritte des Auflösens und Nachrutschens werden wiederholt, bis keine Viererlinie gleicher
Steine mehr existiert. Erst dann kann der nächste Stein von oben in das Spielfeld hineinfallen.
Wenn durch das Nachrutschen mehrere Viererlinien gleichzeitig entstehen, so lösen sich diese
auch gleichzeitig auf.
Ihr Programm soll für eine gegebene Sequenz hereinfallender Steine die Spielmechanik simulieren und den resultierenden Endzustand auszugeben.
In dieser Aufgabe sollen Sie den Kern einer Computerspiel-Engine schreiben. Die Spiel-Mechanik
kann man sich als eine Mischung aus „Vier gewinnt“ und „Candy Crush“ vorstellen: Auf ein
diskretes Spielfeld Z × N0 fallen von oben (aus positiver y-Richtung) nacheinander einzelne
Spielsteine (nachfolgend „Steine“) unterschiedlicher Farben herunter und bilden Stapel. Sobald
vier oder mehr Steine der selben Farbe vertikal, horizontal oder diagonal in einer geraden Linie zusammenhängen, lösen diese sich auf; die darüber liegenden Steine rutschen dann nach
unten nach. Auch wenn ein Stein Teil zweier Viererlinien ist, lösen sich beide auf (z. B. wenn
sieben Steine T-förmig angeordnet sind oder sich zwei Linien in anderer Weise überschneiden).
Die Schritte des Auflösens und Nachrutschens werden wiederholt, bis keine Viererlinie gleicher
Steine mehr existiert. Erst dann kann der nächste Stein von oben in das Spielfeld hineinfallen.
Wenn durch das Nachrutschen mehrere Viererlinien gleichzeitig entstehen, so lösen sich diese
auch gleichzeitig auf.
Ihr Programm soll für eine gegebene Sequenz hereinfallender Steine die Spielmechanik simulieren und den resultierenden Endzustand auszugeben.
input: số đầu tiên là màu của viên đá, số thứ 2 là hoành độ x
1 0
1 1
1 2
0 3
0 -1
0 -2
0 -3
0 -3
3 -2
1 -1
2 0
2 1
2 2
3 3
3 2
3 1
3 0
2 -1
0 -2
0 -1
0 -4
output: màu, hoành độ, tung độ của các viên đá còn lại trên bàn
0 3 0
3 -2 0
3 0 0
3 1 0
3 2 0
3 3 1
constrain: 0 \le color \le 254, |x| \le 2^{20}
tạm thời thì mình đang brutal force, nhưng mà test lên tầm 25k input thì mất khoảng 10 phút
- save bàn chơi vào 1 cái array 2 chiều
- mỗi lần có viên đá mới vào thì kiểm tra toàn bộ array xem có chỗ nào có 4 viên cùng màu không
- nếu có thì xóa xong đẩy mấy viên ở trên xuống
mình có thử chỉ kiểm tra chỗ viên đá mới vào với xung quanh viên đá bị xóa, nhưng mà kết quả không chính xác. mãi không nghĩ ra cách nhanh hơn nên lên đây hóng hớt
code của mình
from time import time
start = time()
field = []
offset = None
def push(col):
count = 0
for i in range(len(col)):
if col[i] != -1:
col[count] = col[i]
count += 1
while count < len(col):
col[count] = -1
count += 1
def drop(field):
found = False
result = []
for i in range(len(field)):
for j in range(len(field[0])):
if field[i][j] == -1:
continue
lines = [(i, j)]
k = i + 1
while k < len(field) and field[k][j] == field[i][j]:
lines.append((k, j))
k += 1
if len(lines) > 3:
result.append(lines)
lines = [(i, j)]
k = j + 1
while k < len(field[0]) and field[i][k] == field[i][j]:
lines.append((i, k))
k += 1
if len(lines) > 3:
result.append(lines)
lines = [(i, j)]
w, h = i+1, j+1
while w < len(field) and h < len(field[0]) and field[w][h] == field[i][j]:
lines.append((w, h))
w += 1
h += 1
if len(lines) > 3:
result.append(lines)
lines = [(i, j)]
w, h = i+1, j-1
while w < len(field) and h > -1 and field[w][h] == field[i][j]:
lines.append((w, h))
w += 1
h -= 1
if len(lines) > 3:
result.append(lines)
pushed = set()
for line in result:
for pos in line:
field[pos[0]][pos[1]] = -1
pushed.add(pos[0])
for col in pushed:
push(field[col])
if result:
found = True
return found
with open("c:\\Users\\tungs\\Downloads\\extra\\test.txt", "r") as f:
for line in f:
data = tuple(map(int, line.split()))
if offset is None:
field.append([data[0]])
offset = data[1]
else:
if data[1] - offset + 1 > len(field):
field += [[-1 for _ in range(len(field[0]))] for _ in range(data[1] - offset + 1 - len(field))]
if offset > data[1]:
field = [[-1 for _ in range(len(field[0]))] for _ in range(offset - data[1])] + field
offset = data[1]
if field[data[1] - offset][-1] != -1:
[f.append(-1) for f in field]
for i in range(len(field[0])):
if field[data[1] - offset][i] == -1:
field[data[1] - offset][i] = data[0]
while drop(field):
pass
break
result = []
for i in range(len(field)):
for j in range(len(field[i])):
if field[i][j] != -1:
result.append((field[i][j], i+offset, j))
result.sort()
for cell in result:
print(*cell)
print(len(result), time()-start)
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?