Cách hiệu quả nhất để quyết định xem không còn di chuyển nào trong trò chơi lưới?

Question

Tôi có một trò chơi đơn giản, nơi bạn có thể di chuyển một mảnh trò chơi 1 hình vuông theo chiều dọc hoặc chiều ngang trong lưới để tạo thành một hàng gồm ba phần cùng loại.

Lưới trò chơi có 8 hình vuông rộng và 7 ô vuông cao, tôi muốn tìm cách hiệu quả nhất để kiểm tra nếu không có di chuyển trái nào sẽ dẫn đến 3 liên tiếp.

Những gì tôi có cho đến nay là:

http://i.imgur.com/jY6wJvZ.png

suy nghĩ của tôi là để kiểm tra theo chiều ngang Tôi chỉ cần kiểm tra cột C không phải là loại mảnh giống như hai bên và tương tự cho cột F.

Theo chiều dọc - Tôi nghĩ hàng 2 chỉ cần được so sánh với hàng 3 để đảm bảo không khớp và cột 5 phải được so sánh với hàng 4 và 6 cho phù hợp.

Vì vậy, nếu không có kết quả nào trong số đó phù hợp thì không thể có thêm động thái nào nữa?

Tôi không chắc đây có phải là cách hiệu quả nhất hoặc nếu nó có thể bỏ lỡ các trận đấu có thể, bất kỳ ai có bộ não tốt hơn tôi đều chỉ cho tôi đúng hướng không?

Answer 1

Séc của bạn không đảm bảo rằng không có di chuyển. Ví dụ, giả sử góc trên cùng bên trái là:

 *  * 
    a a b c . . . . 
* c c a b . . . . 
    b b d a . . . . 
    . . . . . . . . 
* . . . . . . . . 
    . . . . . . . . 
    . . . . . . . . 

Trên thực tế, không có ô trong cột C tương đương với một trong hai bên trái hoặc bên phải của nó, và không có tế bào trong dòng 2 là bằng hoặc trên hoặc dưới nó. Tuy nhiên, chúng ta có thể hoán đổi C1 và C2 để tạo ra 3-trong-một-hàng.

Như @Patashu đề xuất, một giải pháp ngây thơ có thể là tốt nhất ở đây, đặc biệt là để khái niệm hóa, ví dụ: nếu ai đó đọc mã của bạn. Tôi sẽ theo dõi ba ô tại một thời điểm (trong hàng đợi FIFO bị ràng buộc), đầu tiên theo hàng, sau đó theo cột và khi hai trong ba kết quả khớp, hãy kiểm tra 2 đến 6 ô xung quanh có thể được hoán đổi thành thứ ba. Ví dụ,

. . . . . . . . 
    . . * . . * . . 
    . * . a a . * . 
    . . * . . * . . 
    . . . . . . . . 
    . . . . . . . . 
    . . . . . . . . 

hoặc

. . . . . . . . 
    . . . . * . . . 
    . . . a . a . . 
    . . . . * . . . 
    . . . . . . . . 
    . . . . . . . . 
    . . . . . . . . 

hoặc

. . . . . . . . 
    . . . . . . . . 
    . . . . . . . . 
    . . . . . . . . 
    . . . . . . . . 
    . . . . . * . . 
    . . . . * . a a 

Nếu bất kỳ của các * 'ed tế bào phù hợp (ví dụ như a), sau đó bạn biết một 3-trong- một hàng là có thể.

Answer 2

Đây là thuật toán ngây thơ của tôi. Rõ ràng tất cả các truy cập mảng nên tôn trọng kiểm tra giới hạn.

1) Kiểm tra từng màu kiểm tra của lưới, như chỉ trong x giây.s duy nhất trong mô hình sau:

x.x.x. 
.x.x.x 
x.x.x. 
.x.x.x 

Scan nó trong dòng đọc (mỗi x chiều ngang, sau đó đi xuống liên tiếp) (gợi ý: % 2 và * 2 sẽ là bạn của bạn ở đây) làm như sau:

1a) Nếu ngói hiện nay là màu sắc tương tự như gạch một thấp hơn và ở bên phải của tôi, nếu một trong các Xs sau cũng có cùng một màu sắc, đó là một ba liên tiếp:

..... 
..XX. 
.Xx.X 
.X.xX 
..XX. 

1b) Đối với một thấp hơn và bên trái là tương tự:

..... 
.XX.. 
X.xX. 
Xx.X. 
.XX.. 

(Tôi sẽ mã hóa vị trí của X thành bù trừ từ ô trung tâm bạn đang kiểm tra - như trong một mảng như {0, -1}, {- 1, 0}, {- 1, 1 } vv)

(Ngoài ra, bạn có thể triển khai từng mảng 5 đến 5 của 1 để kiểm tra tại đây, 0 cho không - tương tự như cách nhìn trong câu trả lời này - và sau đó quét 5 đến 5 mảng trong khi quét trường chơi. Điều này có thể nhanh hơn. Không ý kiến! Bạn phải kiểm tra.)

2) Bây giờ xuống từng cột, từ trên xuống dưới Nếu hai ô liền kề có màu giống nhau, kiểm tra ô hai hoặc cao hơn - nếu có cùng màu, đó là ba trong một hàng:

. 
X 
. 
x 
x 
. 
X 

3) tương tự cho các hàng, đọc từ trái sang phải:

.X.xx.X 

Lưu ý: tôi không có ý tưởng nếu điều này là nhanh hơn so với thuật toán ngây thơ kiểm tra tất cả các trao đổi có thể xem nếu nó làm cho một trong ba liên tiếp! Sau khi tất cả, cả hai thuật toán là O (n^2), do đó, đó là nhanh hơn sẽ phụ thuộc vào chi tiết thực hiện. Vì vậy, tôi khuyên bạn nên sử dụng hai thứ:

1) Không tối ưu hóa cho đến khi bạn đã triển khai giải pháp và giải pháp quá chậm đối với trường hợp thực tế đang được sử dụng cho những người đang sử dụng.

2) Khi bạn tối ưu hóa, kiểm tra xem bạn đã thực hiện nhanh hơn chưa! (Và cũng đảm bảo rằng nó vẫn hoạt động - không có gì tệ hơn là một tối ưu hóa phá vỡ mã :))

Tất nhiên, điều này không có nghĩa là tối ưu hóa không vui, nhưng không bị lừa khi nghĩ đến việc tối ưu hóa đã đủ nhanh mã đang làm bất cứ điều gì nhưng tập thể dục tâm trí của bạn;)