Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

LINKDIST - Durchschnittliche Link-Distanz zwischen Webseiten

In einer Forschungsarbeit aus dem Jahre 1999 ("The Small World Web") wird gezeigt, dass das World Wide Web die Eigenschaft hat, dass man bei beliebigen, zufällig gewählten Webseiten im Durchschnitt 19 Links folgen muss, um von der einen Webseite auf die andere Webseite zu gelangen. Diese Eigenschaft lässt sich auch bezogen auf einen Graphen interpretieren: Knoten entsprechen Webseiten, Kanten entsprechen Links, und die durchschnittliche Entfernung zwischen je zwei Knoten im Graph entspricht der erwarteten Anzahl an Links, denen man folgen muss um von einer Webseite zu einer anderen Webseite zu gelangen.

In dieser Aufgabe bekommen Sie einen Graphen, für den Sie die durchschnittliche Entfernung zwischen je zwei Knoten bestimmen sollen.

Eingabe

Die erste Zeile der Eingabe enthält eine Zahl n ≤ 200, die Anzahl an Knoten im Graph. Die folgenden n Zeilen enthalten n Zeichen, wobei das j.-te Zeichen in der i.-ten Zeile angibt, ob von Knoten i zu Knoten j eine Verbindung existiert oder nicht. Das Zeichen 'Y' bedeutet, dass die Verbindung existiert, und 'N' bedeutet, dass sie nicht existiert. Sie können annehmen, dass von jedem Knoten zu jedem anderen Knoten ein Pfad existiert.

Ausgabe

Geben Sie die durchschnittliche Länge der kürzesten Wege zwischen je zwei verschiedenen Knoten im Graphen als gekürzten Bruch aus im Format "Zähler/Nenner" (siehe Beispiel).

Beispiel

Eingabe:
4
NYYN
NNNY
YNNN
NNYN

Ausgabe:
11/6

Erklärung zum Beispiel

Die Länge des kürzesten Weges von Knoten 1 zu Knoten 2, 3, und 4 ist 1, 1, bzw. 2. Vom Knoten 2 zu den Knoten 1, 3 und 4 haben die kürzesten Wege die Längen 3, 2, und 1, vom Knoten 3 zu den Knoten 1, 2, und 4 die Längen 1, 2, und 3. Vom Knoten 4 zu den Knoten 1, 2, und 3 haben die kürzesten Wege die Längen 2, 3, und 1. Die Summe dieser Pfadlängen ist 1 + 1 + 2 + 3 + 2 + 1 + 1 + 2 + 3 + 2 + 3 + 1 = 22. Da es 12 Paare von Knoten gibt, zwischen denen die kürzesten Wege berechnet werden, ergibt sich eine durchschnittliche Pfadlänge von 22/12, was als gekürzter Bruch 11/6 ergibt.


Added by:Adrian Kuegel
Date:2008-12-15
Time limit:1s-10s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C CSHARP C++ 4.3.2 CPP C99 CLOJURE LISP sbcl LISP clisp D FSHARP FORTRAN GO HASK JAVA LUA OCAML PERL PHP PRLG-swi PYTHON PYTHON3 PY_NBC RUBY SCALA
Resource:ACM ICPC World Finals 2000

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.