Jawaban lainnya sudah cukup panjang, jadi saya membiarkannya apa adanya. Jawaban ini jauh lebih baik, lebih sederhana, dan juga benar sedangkan yang lain memiliki beberapa kasus tepi yang akan menghasilkan jawaban yang salah - saya akan menyerahkan latihan itu kepada pembaca.
Catatan:Hentian baris ditambahkan untuk kejelasan. Seluruh blok adalah satu kueri
;with Walker(StartX,StartY,X,Y,Visited) as (
select X,Y,X,Y,CAST('('+right(X,3)+','+right(Y,3)+')' as Varchar(Max))
from puzzle
union all
select W.StartX,W.StartY,P.X,P.Y,W.Visited+'('+right(P.X,3)+','+right(P.Y,3)+')'
from Walker W
join Puzzle P on
(W.X=P.X and W.Y=P.Y+1 OR -- these four lines "collect" a cell next to
W.X=P.X and W.Y=P.Y-1 OR -- the current one in any direction
W.X=P.X+1 and W.Y=P.Y OR
W.X=P.X-1 and W.Y=P.Y)
AND W.Visited NOT LIKE '%('+right(P.X,3)+','+right(P.Y,3)+')%'
)
select X, Y, Visited
from
(
select W.X, W.Y, W.Visited, rn=row_number() over (
partition by W.X,W.Y
order by len(W.Visited) desc)
from Walker W
left join Walker Other
on Other.StartX=W.StartX and Other.StartY=W.StartY
and (Other.Y<W.Y or (Other.Y=W.Y and Other.X<W.X))
where Other.X is null
) Z
where rn=1
Langkah pertama adalah menyiapkan ekspresi tabel rekursif "walker" yang akan dimulai di setiap sel dan berjalan sejauh mungkin tanpa menelusuri kembali langkah apa pun. Memastikan bahwa sel tidak dikunjungi kembali dilakukan dengan menggunakan kolom yang dikunjungi, yang menyimpan setiap sel yang telah dikunjungi dari setiap titik awal. Secara khusus, kondisi ini AND W.Visited NOT LIKE '%('+right(P.X,3)+','+right(P.Y,3)+')%'
menolak sel yang telah dikunjunginya.
Untuk memahami cara kerja sisanya, Anda perlu melihat hasil yang dihasilkan oleh CTE "Walker" dengan menjalankan "Pilih * dari pesanan Walker oleh StartX, StartY" setelah CTE. "Potongan" dengan 5 sel muncul di setidaknya 5 grup, masing-masing dengan (StartX,StartY)
yang berbeda , tetapi setiap grup memiliki 5 (X,Y)
potongan dengan jalur "Dikunjungi" yang berbeda.
Subquery (Z) menggunakan LEFT JOIN + IS NULL untuk menyiangi grup ke baris tunggal di setiap grup yang berisi "koordinat XY pertama", yang ditentukan oleh kondisi
Other.StartX=W.StartX and Other.StartY=W.StartY
and (Other.Y<W.Y or (Other.Y=W.Y and Other.X<W.X))
Tujuannya adalah untuk setiap sel yang dapat dikunjungi mulai dari (StartX, StartY), untuk membandingkan satu sama lain sel dalam kelompok yang sama, dan untuk menemukan sel di mana TIDAK ADA sel LAIN pada baris yang lebih tinggi, atau jika mereka berada di baris yang sama, berada di sebelah kiri sel ini. Namun, ini masih memberi kami terlalu banyak hasil. Pertimbangkan hanya potongan 2 sel di (3,4) dan (4,4):
StartX StartY X Y Visited
3 4 3 4 (3,4) ******
3 4 4 4 (3,4)(4,4)
4 4 4 4 (4,4)
4 4 3 4 (4,4)(3,4) ******
2 baris tetap dengan "koordinat XY pertama" dari (3,4), ditandai dengan ******
. Kami hanya membutuhkan satu baris, jadi kami menggunakan Row_Number dan karena kami penomoran, kami mungkin juga menggunakan Visited
terpanjang jalan, yang akan memberi kita banyak sel-sel di dalam potongan yang bisa kita dapatkan.
Kueri luar terakhir hanya mengambil baris pertama (RN=1) dari setiap grup (X,Y) yang serupa.
Untuk menampilkan SEMUA sel dari setiap bagian, ubah barisselect X, Y, Visited
di tengah ke
select X, Y, (
select distinct '('+right(StartX,3)+','+right(StartY,3)+')'
from Walker
where X=Z.X and Y=Z.Y
for xml path('')
) PieceCells
Yang memberikan output ini
X Y PieceCells
1 1 (1,1)(2,1)(2,2)(3,2)
3 4 (3,4)(4,4)
5 6 (5,6)
7 5 (7,5)(8,5)(9,5)
8 1 (10,1)(8,1)(8,2)(9,1)(9,2)(9,3)