P2749 [IOI 1998 / USACO5.1] Starry Night

High in the night sky, clusters of shining stars form countless shapes. A cluster is a non-empty connected group of stars, where connectivity means two stars are adjacent horizontally, vertically, or diagonally (8-neighbor connectivity). A cluster cannot be part of a larger cluster. Clusters can be similar. If two clusters have the same shape and contain the same number of stars, then regardless of their orientation, they are considered similar. In general, there are eight possible orientations for a cluster, as shown in Figure $1$. 

The night sky can be represented as a sky map, which is a 2D matrix of characters `0` and `1`. A character `1` indicates there is a star at that position; a character `0` indicates the position is empty. Given a sky map, use the same lowercase English letter to mark all similar clusters. Similar clusters must be marked with the same letter, and different clusters must be marked with different letters. To mark a cluster, replace each `1` corresponding to a star in that cluster with the appropriate lowercase letter.

The first two lines contain the width $W$ and the height $H$ of the sky map, respectively. The sky map then follows in the next $H$ lines, each containing $W$ characters.

Output the sky map after marking the clusters (in the same format as the input, except that clusters are marked). For the same input, there may be many valid markings; in that case, output the lexicographically smallest marking.

### Sample Explanation In this case, the sky map is a 2D matrix with length $23$ and width $15$. The input corresponds to the following image of the matrix.  The output corresponds to the following view of the night sky.  ### Constraints - $0 \le$ the length and width of the sky map $\le 100$. - $0 \le$ the number of clusters $\le 500$. - $0 \le$ the number of dissimilar clusters $\le 26$. - $1 \le$ the number of stars in each cluster $\le 160$. Translated by ChatGPT 5