/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
ストーリー
高橋市の高橋市長は市役所のロビーの床に色の付いた正方形タイルを用いて高橋市の地図を描くことにした。 高橋市はいくつかの区に別れており、この地図では各区は同じ色の連結なタイルの集合として表現する。 業者に依頼して正確な地図の案を作成したところ、使用するタイル数が多く、予算オーバーとなってしまった。 グラフが大好きな高橋市長は、区の間の隣接関係にしか興味がなく、各区の形状や大きさなど隣接関係以外の情報を無視すればより少ないタイル数で地図が描けるのではと考えている。 使用するタイル数が出来るだけ少ない地図を作成して欲しい。
正確な地図
隣接関係を正しく表現した小さな地図
問題文
n\times n マスのグリッド上に表現された高橋市の地図が与えられる。 一番左上のマスの座標を (0,0) とし、そこから下方向に i マス、右方向に j マス移動した先のマスの座標を (i,j) とする。 高橋市は m 個の区からなり、c (1\leq c\leq m) 番の色で塗られたマスは c 番の区に対応する。 n\times n マスの外は市の外部であり、0 番の色で塗られているものとする。
2つのマスは辺を共有する場合に「隣接している」と定義し、マス集合は隣接するマスを経由して互いに到達可能な場合に「連結である」と定義される。 与えられた地図は、各色について、その色で塗られたマス集合は連結であることが保証されている。
n\times n マスのグリッド上に表現された地図であって、以下の条件を全て満たすものを作成せよ。
- 全ての色 c (0\leq c\leq m) について、色 c のマスは連結である。ただし、n\times n マスの外部は色 0 で塗られているため、色 0 のマスは外部のマスを経由して連結であれば良い。
- 全ての色 c,d (0\leq c<d\leq m) に対して、元の地図と作成した地図で色 c のマス集合と色 d のマス集合の隣接関係が等しい。すなわち、元の地図で色 c で塗られたマスに隣接する色 d で塗られたマスが存在する場合、そしてその場合に限り、作成した地図においても 色 c のマスとそれに隣接する色 d のマスが存在する。ただし、n\times n マスの外部は全て色 0 で塗られているため、外周上のマスは色 0 のマスと隣接しているとみなす。
得点
作成した地図に含まれる色 0 のマスの総数を E としたとき、E+1 の得点が得られる。
テストケースは全部で 150 個あり、各テストケースの得点の合計が提出の得点となる。 一つ以上のテストケースで不正な出力や制限時間超過をした場合、提出全体の判定がWAやTLEとなる。 コンテスト時間中に得た最高得点で最終順位が決定され、コンテスト終了後のシステムテストは行われない。 同じ得点を複数の参加者が得た場合、提出時刻に関わらず同じ順位となる。
入力
入力は以下の形式で標準入力から与えられる。
n m
c_{0,0} c_{0,1} \cdots c_{0,n-1}
\vdots
c_{n-1,0} c_{n-1,1} \cdots c_{n-1,n-1}
全てのテストケースで n = 50, m = 100 で固定である。 c_{i,j} は座標 (i,j) のマスの色を表す整数値であり、1\leq c_{i,j}\leq m を満たす。 各 k=1,2,\cdots,m に対して、c_{i,j}=k であるような (i,j) が一つ以上存在する。
出力
作成した地図における座標 (i,j) のマスの色を d_{i,j} (0\leq d_{i,j}\leq m) としたとき、以下の形式で標準出力に出力せよ。
d_{0,0} d_{0,1} \cdots d_{0,n-1}
\vdots
d_{n-1,0} d_{n-1,1} \cdots d_{n-1,n-1}
出力された地図が問題文に記された条件を満たさない場合、WA と判定される。
プログラムは解を複数回出力しても良い。 複数回出力された場合、一番最後の解のみが採点に用いられる。 Web版のビジュアライザを使用すると、複数の解の比較が可能である。
入力生成方法
c_{i,j}=0 であるマスをランダムに一つ選び、そのマスに隣接するマス (i',j') をランダムに選ぶ。 c_{i,j}=c_{i',j'} と設定する。
ツール(入力ジェネレータ・ビジュアライザ)
- Web版: ローカル版より高性能でアニメーション表示と手動プレイが可能です。
- ローカル版: 使用するにはRust言語のコンパイル環境をご用意下さい。
- Windows用のコンパイル済みバイナリ: Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。
コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。ご注意下さい。
Story
Mr. Takahashi, the mayor of Takahashi City, decided to draw a map of Takahashi City on the floor of the city hall lobby using colored square tiles. Takahashi City is divided into several wards, and in this map, each ward should be represented as a set of connected tiles of the same color. He commissioned a contractor to create a draft of an accurate map, but the number of tiles to be used was too large, and the budget was exceeded. Mayor Takahashi, who loves graphs, is only interested in the adjacencies between the wards and thinks that the map could be drawn with fewer tiles if information other than adjacencies, such as the shape and size of each ward, is ignored. Please create a map using as few tiles as possible.
Accurate map
Small map correctly representing adjacencies
Problem Statement
Given a map of Takahashi City represented on a grid of n\times n squares. Let (0,0) be the coordinates of the top-left square, and (i,j) be the coordinates of the square located i squares down and j squares to the right from there. The city consists of m wards, and the square of color c (1\leq c\leq m) corresponds to the c-th ward. The outside of the n\times n squares correspond to the outside of the city and is colored 0.
Two squares are defined as "adjacent" if they share an edge, and a set of squares is defined as "connected" if any two squares can reach each other via adjacent squares. In the given map, for each color c, the set of squares of color c is guaranteed to be connected.
Your task is to create a map represented on a grid of n\times n squares that satisfies all of the following conditions.
- For every color c (0\leq c\leq m), squares of color c must be connected. Note that since the outside of the n\times n squares is colored 0, squares of color 0 can be connected through the outside squares.
- For every pair of colors c and d (0\leq c<d\leq m), the adjacency of a set of squares of color c and a set of squares of color d in the original map and the created map must be identical. That is, if and only if there exist adjacent squares of color c and d in the original map, there exist adjacent squares of color c and d in the created map. Note that since the outside of the n\times n squares is colored 0, the squares on the boundary are considered to be adjacent to squares of color 0.
Scoring
Let E be the total number of squares of color 0 in the created map. Then you will obtain a score of E+1.
There are 150 test cases, and the score of a submission is the total score for each test case. If your submission produces an illegal output or exceeds the time limit for some test cases, the submission itself will be judged as WA or TLE , and the score of the submission will be zero. The highest score obtained during the contest will determine the final ranking, and there will be no system test after the contest. If more than one participant gets the same score, they will be ranked in the same place regardless of the submission time.
Input
Input is given from Standard Input in the following format.
n m
c_{0,0} c_{0,1} \cdots c_{0,n-1}
\vdots
c_{n-1,0} c_{n-1,1} \cdots c_{n-1,n-1}
For all test cases, we fix n = 50 and m = 100. c_{i,j} is an integer value representing the color of the square at coordinates (i,j) and satisfies 1\leq c_{i,j}\leq m. For every k=1,2,\cdots,m, there exists at least one (i,j) with c_{i,j}=k.
Output
Let d_{i,j} (0\leq d_{i,j}\leq m) be the color of the square at coordinates (i,j) in the created map. Then, output to Standard Output in the following format.
d_{0,0} d_{0,1} \cdots d_{0,n-1}
\vdots
d_{n-1,0} d_{n-1,1} \cdots d_{n-1,n-1}
If the output map does not satisfy the conditions specified in the problem statement, the submission will be judged as WA.
Your program may output multiple solutions. If multiple solutions are output, only the last one is used for scoring. You can compare multiple solutions using the web version of the visualizer.
Input Generation
Randomly select a square with c_{i,j}=0 and randomly select its adjacent square (i',j'). We set c_{i,j}=c_{i',j'}.
Tools (Input generator and visualizer)
- Web version: This is more powerful than the local version providing animations and manual play.
- Local version: You need a compilation environment of Rust language.
- Pre-compiled binary for Windows: If you are not familiar with the Rust language environment, please use this instead.
Please be aware that sharing visualization results or discussing solutions/ideas during the contest is prohibited.