Tantangan

Diberi matriks bilangan bulat positif, tentukan apakah ada "cincin" gunung. Definisi formal untuk tantangan ini adalah: diberi matriks bilangan bulat positif, apakah ada bilangan bulat positif nyang ada cincin sel tertutup dalam matriks yang benar-benar lebih besar dari nsehingga semua sel yang tertutup dalam cincin kurang dari atau sama dengan untuk n.

Mari kita ambil contoh yang benar:

3 4 5 3
3 1 2 3
4 2 1 3
4 3 6 5

Jika kita mengatur nke 2:

1 1 1 1
1 0 0 1
1 0 0 1
1 1 1 1

Seperti yang dapat kita lihat dengan jelas, 1garis tepi sepanjang membentuk cincin.

Kami mendefinisikan cincin sebagai kumpulan sel yang terurut di mana sel-sel yang berdekatan dalam koleksi juga berdekatan (tepi atau sudut) pada kisi. Selain itu, cincin harus mengandung setidaknya 1 sel di dalamnya; yaitu, mencoba melakukan edge-only BFS-flofill seluruh matriks tidak termasuk sel dalam koleksi dan tidak pernah melintasi sel dalam koleksi harus kehilangan setidaknya satu sel.

Kasus Uji Kebenaran

4 7 6 5 8 -> 1 1 1 1 1
6 2 3 1 5 -> 1 0 0 0 1 (n = 3)
6 3 2 1 5 -> 1 0 0 0 1
7 5 7 8 6 -> 1 1 1 1 1

1 3 2 3 2
1 6 5 7 2
1 7 3 7 4
1 6 8 4 6

1 3 1
3 1 3
1 3 1

7 5 8 7 5 7 8 -> if you have n = 4, you get an interesting ridge shape around the top and right of the grid
8 4 4 2 4 2 7
6 1 8 8 7 2 7
5 4 7 2 5 3 5
5 6 5 1 6 4 5
3 2 3 2 7 4 8
4 4 6 7 7 2 5
3 2 8 2 2 2 8
2 4 8 8 6 8 8

5 7 6 8 6 8 7 -> there is an island in the outer ring (n = 4), but the island is a ring
5 3 2 4 2 4 7
6 3 7 8 5 1 5
8 2 5 2 8 2 7
8 3 8 8 8 4 7
6 1 4 1 1 2 8
5 5 5 5 7 8 7

150 170 150
170 160 170
150 170 150

Kasus Uji Falsy

1 2 3 2 1 -> this is just a single mountain if you picture it graphcially
2 3 4 3 2
3 4 5 4 3
2 3 4 3 2
1 2 3 2 1

4 5 4 3 2 -> this is an off-centered mountain
5 6 5 4 3
4 5 4 3 2
3 4 3 2 1

1 1 1 1 1 -> this is four mountains, but they don't join together to form a ring
1 2 1 2 1
1 1 1 1 1
1 2 1 2 1
1 1 1 1 1

3 3 3 3 3 -> there is a ring formed by the `3`s, but the `4` in the middle is taller so it doesn't qualify as a mountain ring
3 1 1 1 3
3 1 4 1 3
3 1 1 1 3
3 3 3 3 3

3 4 4 4 3
4 4 3 4 4
3 3 3 3 4
4 4 3 4 4
3 4 4 4 3

1  2  3  4  5
6  7  8  9  10
11 12 13 14 15
16 17 18 19 20
22 23 24 25 26

Aturan

• Celah Standar Berlaku
• Ini adalah kode-golf , jadi jawaban terpendek dalam byte di setiap bahasa dinyatakan sebagai pemenang bahasa. Tidak ada jawaban yang akan diterima.
• Input dapat diambil sebagai bentuk yang masuk akal untuk matriks bilangan bulat positif
• Keluaran dapat diberikan sebagai dua nilai wajar, konsisten, berbeda yang menunjukkan [benar] atau [salah].

Jelly , 38 byte

Ẇ€Z$⁺Ẏµ,ZẈ>2ẠµƇµḊṖZƊ⁺FṀ<,Z.ịḊṖ$€Ɗ€ƊȦ)Ṁ

Cobalah online!

Output 1 jika matriks berisi rentang gunung, 0 sebaliknya.

Cara kerjanya (agak ketinggalan jaman)

Saya mungkin dapat mempersingkat kode sedikit, jadi bagian ini mungkin akan mengalami pengeditan berat.

Tautan pembantu

,Z.ịḊṖ$€Ɗ€ – Helper link. Let S be the input matrix.
,Z         – Pair S with its transpose.
        Ɗ€ – For each matrix (S and Sᵀ), Apply the previous 3 links as a monad.
  .ị       – Element at index 0.5; In Jelly, the ị atom returns the elements at
             indices floor(x) and ceil(x) for non-integer x, and therefore this
             returns the 0th and 1st elements. As Jelly is 1-indexed, this is the
             same as retrieving the first and last elements in a list.
    ḊṖ$€   – And for each list, remove the first and last elements.

Misalnya diberi matriks dalam bentuk:

A(1,1) A(1,2) A(1,3) ... A(1,n)
A(2,1) A(2,2) A(2,3) ... A(2,n)
A(3,1) A(3,2) A(3,3) ... A(3,n)
...
A(m,1) A(m,2) A(m,3) ... A(m,n)

Ini mengembalikan array (urutannya tidak masalah):

A(1,2), A(1,3), ..., A(1,n-1)
A(m,2), A(m,3), ..., A(m,n-1)
A(2,1), A(3,1), ..., A(m-1,1)
A(2,n), A(3,n), ..., A(m-1,n)

Singkat cerita, ini menghasilkan baris dan kolom terluar, dengan sudut dihapus.

Tautan utama

Ẇ€Z$⁺Ẏµ,ZẈ>2ẠµƇµḊṖZƊ⁺FṀ<ÇȦ)Ṁ – Main link. Let M be the input matrix.
Ẇ€                           – For each row of M, get all its sublists.
  Z$                         – Transpose and group into a single link with the above.
    ⁺                        – Do twice. So far, we have all contiguous sub-matrices.
     Ẏ                       – Flatten by 1 level.
      µ      µƇ              – Filter-keep those that are at least 3 by 3:
       ,Z                      – Pair each sub-matrix S with Sᵀ.
         Ẉ                     – Get the length of each (no. rows, no. columns).
          >2                   – Element-wise, check if it's greater than 2.
            Ạ                  – All.
               µ          )  – Map over each sub-matrix S that's at least 3 by 3
                ḊṖ           – Remove the first and last elements.
                  ZƊ         – Zip and group the last 3 atoms as a single monad.
                    ⁺        – Do twice (generates the inner cells).
                     FṀ      – Flatten, and get the maximum.
                       <Ç    – Element-wise, check if the results of the helper
                               link are greater than those in this list.
                         Ȧ   – Any and all. 0 if it is empty, or contains a falsey
                               value when flattened, else 1.
                           Ṁ – Maximum.

Bersihkan , 224 ... 161 byte

import StdEnv,StdLib
p=prod
~ =map
^ =reverse o$
@ =transpose o~(^o^)
$l=:[h:t]|h>1=l=[1: $t]
$e=e
?m=p[p(~p(limit(iterate(@o@)(~(~(\a|a>b=2=0))m))))\\n<-m,b<-n]

Cobalah online!

Menentukan fungsi ? :: [[Int]] -> Int, mengembalikan 0jika ada dering, dan 1sebaliknya.

Bekerja dengan mengubah matriks menjadi 2s untuk gunung dan 0s untuk lembah, lalu banjir dengan 1s sampai hasilnya berhenti berubah. Jika ada 0yang masih ada untuk ketinggian gunung apa pun, produk akan menjadi 0.

JavaScript (Node.js) , 302 byte

a=>a.some((b,i)=>b.some((n,j)=>(Q=(W=(i,j,f)=>[a.map((b,I)=>b.map((t,J)=>I==i&J==j)),...a+0].reduce(A=>A.map((b,I)=>b.map((t,J)=>f(I)(J)&&(A[I-1]||b)[J]|(A[I+1]||b)[J]|b[J-1]|b[J+1]|t))))(i,j,I=>J=>a[I][J]<=n)).some((b,i)=>b.some((d,j)=>d&&!i|!j|!Q[i+1]|b[j+1]==b.b))<!/0/.test(W(0,0,I=>J=>!Q[I][J]))))

Cobalah online!

Cek apakah mengalir dari suatu titik tidak dapat mencapai perbatasan, sementara perbatasan dapat berjalan ke setiap titik