XY-Sort 〜 横へな 2013.2.2 の参考問題

問題

下図のような表を行(A行〜F行)または列(u列〜z列)について整列する。
整列した結果出来上がった表の一番上の行(A行)を出力する。


u v w x y z
A 4 1 4 2 1 3
B 7 3 2 0 5 0
C 2 3 6 0 6 7
D 6 4 5 7 5 1
E 3 1 6 6 2 4
F 6 0 5 5 5 1

整列は昇順（A行〜F行で整列する場合は右に行くほど大きくなるように、u列〜z列で整列する場合は下に行くほど大きくなるように）で行う。
整列は、安定ソートで行う。つまり、キーとなる行・列の値では順位が定まらない場合、元の順序を保存する。

入力と操作

A〜F は、その行の値をキーにして整列することを意味する。
u〜z は、その列の値をキーにして整列することを意味する。

計算例

入力が AvEx である場合を考える。

u v w x y z
A 4 1 4 2 1 3
B 7 3 2 0 5 0
C 2 3 6 0 6 7
D 6 4 5 7 5 1
E 3 1 6 6 2 4
F 6 0 5 5 5 1
→
A行で
整列
u v w x y z
A 1 1 2 3 4 4
B 3 5 0 0 7 2
C 3 6 0 7 2 6
D 4 5 7 1 6 5
E 1 2 6 4 3 6
F 0 5 5 1 6 5
→
v列で
整列
u v w x y z
A 1 1 2 3 4 4
B 1 2 6 4 3 6
C 3 5 0 0 7 2
D 4 5 7 1 6 5
E 0 5 5 1 6 5
F 3 6 0 7 2 6
→
E行で
整列
u v w x y z
A 1 3 1 2 4 4
B 1 4 2 6 6 3
C 3 0 5 0 2 7
D 4 1 5 7 5 6
E 0 1 5 5 5 6
F 3 7 6 0 6 2
→
x列で
整列
u v w x y z
A 3 0 5 0 2 7
B 3 7 6 0 6 2
C 1 3 1 2 4 4
D 0 1 5 5 5 6
E 1 4 2 6 6 3
F 4 1 5 7 5 6

一連の操作を終えたあとのA行の内容をひとまとまりにした、 305027 が出力すべき文字列となる。


実装ができた方は Qiitaの記事 のコメント欄からリンクを張っていただくと見つけやすくて助かります。

サンプルデータ

# 入力 期待
0 AvEx 305027
1 A 112344
2 C 241413
3 F 134214
4 u 236067
5 w 732050
6 y 414213
7 yx 732050
8 ux 236067
9 EF 131424
10 DF 134124
11 Au 055165
12 uA 023667
13 By 234114
14 yB 114342
15 yBy 357020
16 yByB 350072
17 AuBvCw 131244
18 FAuFBvFCw 300527
19 AuBv 112344
20 CwDx 515056
21 FzyE 324114
22 uAwDyB 114324
23 zExCvF 073520
24 uFxEv 002357
25 DyCwB 076362

C/C++/Java 用のテストデータ