Die andere Antwort ist schon ziemlich lang, also lasse ich sie so wie sie ist. Diese Antwort ist viel besser, einfacher und auch richtig, während die andere einige Randfälle hat, die zu einer falschen Antwort führen - ich überlasse diese Übung dem Leser.
Hinweis:Zeilenumbrüche wurden zur Verdeutlichung hinzugefügt. Der gesamte Block ist eine einzige Abfrage
;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
Der erste Schritt besteht darin, einen rekursiven "Walker"-Tabellenausdruck einzurichten, der bei jeder Zelle beginnt und sich so weit wie möglich bewegt, ohne einen Schritt zurückzuverfolgen. Um sicherzustellen, dass Zellen nicht erneut besucht werden, wird die besuchte Spalte verwendet, die jede Zelle speichert, die von jedem Startpunkt aus besucht wurde. Insbesondere diese Bedingung AND W.Visited NOT LIKE '%('+right(P.X,3)+','+right(P.Y,3)+')%' weist bereits besuchte Zellen zurück.
Um zu verstehen, wie der Rest funktioniert, müssen Sie sich das vom „Walker“-CTE generierte Ergebnis ansehen, indem Sie „Select * from Walker order by StartX, StartY“ nach dem CTE ausführen. Ein "Stück" mit 5 Zellen erscheint in mindestens 5 Gruppen, jede mit einem anderen (StartX,StartY) , aber jede Gruppe hat alle 5 (X,Y) Stücke mit unterschiedlichen "Besuchten" Pfaden.
Die Unterabfrage (Z) verwendet einen LEFT JOIN + IS NULL, um die Gruppen bis auf die einzelne Zeile in jeder Gruppe herunterzufiltern, die die „erste XY-Koordinate“ enthält, die durch die Bedingung definiert ist
Other.StartX=W.StartX and Other.StartY=W.StartY
and (Other.Y<W.Y or (Other.Y=W.Y and Other.X<W.X))
Die Absicht besteht darin, jede Zelle, die ab (StartX, StartY) besucht werden kann, mit jeder anderen Zelle in derselben Gruppe zu vergleichen und die Zelle zu finden, in der sich KEINE ANDERE Zelle in einer höheren Zeile befindet, oder wenn sie sich in der befinden dieselbe Zeile, befindet sich links von dieser Zelle. Dies lässt uns jedoch immer noch mit zu vielen Ergebnissen zurück. Betrachten Sie nur ein 2-Zellen-Stück bei (3,4) und (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) ******
Es bleiben 2 Zeilen mit der "ersten XY-Koordinate" von (3,4), markiert mit ****** . Wir brauchen nur eine Zeile, also verwenden wir Row_Number und da wir nummerieren, können wir genauso gut den längsten Visited wählen Pfad, der uns so viele von geben würde die Zellen innerhalb des Stücks, wie wir bekommen können.
Die letzte äußere Abfrage nimmt einfach die ersten Zeilen (RN=1) aus jeder ähnlichen (X,Y)-Gruppe.
Um ALLE Zellen jedes Teils anzuzeigen, ändern Sie die Zeileselect X, Y, Visited
in der Mitte bis
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
Welche geben diese Ausgabe
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)
