Fish

source: 12th Japanese Olympiad in Informatics, Preliminary Round

raw_problem:
魚の生息範囲 (Fish)

  問題

オーストラリア大陸の西には，広いインド洋が広がっている．海洋研究者である JOI 氏は，インド洋に生息しているある N 種類の魚の性質について研究している．

それぞれの魚の種類に対して，海の中に直方体状の生息範囲が定まっている．魚は境界も含めて生息範囲の中のどの場所にも移動できるが，生息範囲の外に出ることは決してない．海の中の点は，3 つの実数 (x, y, d) によって表される： (x, y, d) は，上空から見たときにある地点を基準にして東に x，北に y 進んだ位置であり，海面からの深さが d の点を表す．ただし，海面は平面であるとする．

JOI 氏は，K 種類以上の魚の生息範囲が重なる場所がどのくらいあるかを知りたい．そのような場所全体の体積を求めるプログラムを作成せよ．

  入力

入力は 1 + N 行からなる．

1 行目には，2 つの整数 N, K (1 ≦ K ≦ N ≦ 50) が空白を区切りとして書かれている．これは，魚が N 種類であり，K 種類以上の魚の生息範囲が重なる場所の体積を求めたいことを表す．

続く N 行のうちの i 行目 (1 ≦ i ≦ N) には，6 つの整数 Xi,1, Yi,1, Di,1, Xi,2, Yi,2, Di,2 (0 ≦ Xi,1 ＜ Xi,2 ≦ 1000000 (= 106)，0 ≦ Yi,1 ＜ Yi,2 ≦ 1000000 (= 106)，0 ≦ Di,1 ＜ Di,2 ≦ 1000000 (= 106)) が書かれている．これは，i 種類目の魚の生息範囲が

8 点 (Xi,1, Yi,1, Di,1), (Xi,2, Yi,1, Di,1), (Xi,2, Yi,2, Di,1), (Xi,1, Yi,2, Di,1), (Xi,1, Yi,1, Di,2), (Xi,2, Yi,1, Di,2), (Xi,2, Yi,2, Di,2), (Xi,1, Yi,2, Di,2) を頂点とする直方体であることを表す．

  出力

K 種類以上の魚の生息範囲が重なる場所全体の体積を 1 行で出力せよ．

  入出力例

入力例 1

3 2
30 50 0 50 70 100
10 20 20 70 90 60
40 60 20 90 90 70

出力例 1

49000

入出力例 1 において，例えば，点 (45, 65, 65) は 1 種類目の魚と 3 種類目の魚の生息範囲であるので，条件を満たす場所である．一方，点 (25, 35, 45) は 2 種類目の魚のみの生息範囲であるので，条件を満たす場所ではない．また，魚の生息範囲は下の図のようになっている．点 O は海面上の基準の地点を表す．

入力例 2

1 1
0 0 0 1000000 1000000 1000000

出力例 2

1000000000000000000

問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。

solutions: ["def main():\n  n, k = map(int, input().split())\n  \n  plst = []\n  xlst = []\n  ylst = []\n  dlst = []\n  \n  for i in range(n):\n    x1,y1,d1,x2,y2,d2 = map(int, input().split())\n    plst.append((x1,y1,d1,x2,y2,d2))\n    xlst.append(x1)\n    xlst.append(x2)\n    ylst.append(y1)\n    ylst.append(y2)\n    dlst.append(d1)\n    dlst.append(d2)\n  \n  xlst = list(set(xlst))\n  ylst = list(set(ylst))\n  dlst = list(set(dlst))\n  \n  xlst.sort()\n  ylst.sort()\n  dlst.sort()\n\n  lx = len(xlst)\n  ly = len(ylst)\n  ld = len(dlst)\n  \n  xdic = {}\n  ydic = {}\n  ddic = {}\n  \n  for i, v in enumerate(xlst):\n    xdic[v] = i\n  for i, v in enumerate(ylst):\n    ydic[v] = i\n  for i, v in enumerate(dlst):\n    ddic[v] = i\n  \n  new_map = [[[0] * ld for _ in range(ly)] for _ in range(lx)]\n  \n  for p in plst:\n    x1, y1, d1, x2, y2, d2 = p\n    x1, y1, d1, x2, y2, d2 = xdic[x1], ydic[y1], ddic[d1], xdic[x2], ydic[y2], ddic[d2]\n    for x in range(x1, x2):\n      for y in range(y1, y2):\n        for d in range(d1, d2):\n          new_map[x][y][d] += 1\n  \n  ans = 0\n  for i in range(lx - 1):\n    xlsti = xlst[i]\n    xlsti1 = xlst[i + 1]\n    x = xdic[xlsti]\n    for j in range(ly - 1):\n      ylstj = ylst[j]\n      ylstj1 = ylst[j + 1]\n      y = ydic[ylstj]\n      for z in range(ld - 1):\n        dlstz = dlst[z]\n        dlstz1 = dlst[z + 1]\n        d = ddic[dlstz]\n        if new_map[x][y][d] >= k:\n          ans += (xlsti1 - xlsti) * (ylstj1 - ylstj) * (dlstz1 - dlstz)\n  print(ans)\n\nmain()\n", "import sys\nfrom bisect import bisect_left\n\n# READ_FROM_FILE = True\nREAD_FROM_FILE = False\n\n\ndef main():\n    if READ_FROM_FILE:\n        f = open('test0.txt', 'r')\n    else:\n        f = sys.stdin\n\n    num_fish_types, k = map(int, f.readline().split())\n    rect_list = []\n    x_set = set()\n    y_set = set()\n    d_set = set()\n    for _ in range(num_fish_types):\n        x0, y0, d0, x1, y1, d1 = map(int, f.readline().split())\n        rect_list.append((x0, y0, d0, x1, y1, d1))\n        x_set.add(x0)\n        x_set.add(x1)\n        y_set.add(y0)\n        y_set.add(y1)\n        d_set.add(d0)\n        d_set.add(d1)\n\n    x_list = sorted(x_set)\n    y_list = sorted(y_set)\n    d_list = sorted(d_set)\n\n    l_rl = len(rect_list)\n    for i in range(l_rl):\n        x0, y0, d0, x1, y1, d1 = rect_list[i]\n        nx0 = bisect_left(x_list, x0)\n        ny0 = bisect_left(y_list, y0)\n        nd0 = bisect_left(d_list, d0)\n        nx1 = bisect_left(x_list, x1)\n        ny1 = bisect_left(y_list, y1)\n        nd1 = bisect_left(d_list, d1)\n        rect_list[i] = (nx0, ny0, nd0, nx1, ny1, nd1)\n\n    lx = len(x_list)\n    ly = len(y_list)\n    ld = len(d_list)\n\n    grid = [[[0] * lx for _ in range(ly)] for _ in range(ld)]\n\n    for i in range(l_rl):\n        nx0, ny0, nd0, nx1, ny1, nd1 = rect_list[i]\n\n        for ny in range(ny0, ny1):\n            for nx in range(nx0, nx1):\n                grid[nd0][ny][nx] += 1\n                grid[nd1][ny][nx] -= 1\n\n    total_area = 0\n    for ny in range(ly - 1):\n        dy = y_list[ny + 1] - y_list[ny]\n        for nx in range(lx - 1):\n            dx = x_list[nx + 1] - x_list[nx]\n            cum_sum = 0\n            for nd in range(ld - 1):\n                cum_sum += grid[nd][ny][nx]\n                if cum_sum >= k:\n                    dd = d_list[nd + 1] - d_list[nd]\n                    total_area += dd * dy * dx\n    print(total_area)\n\n    return\n\n\nif __name__ == '__main__':\n    main()\n\n", "# \u9b5a\u306e\u751f\u606f\u7bc4\u56f2 (Fish)\n# \u5ea7\u6a19\u5727\u7e2e\n# \u89e3\u3051\u306a\u304b\u3063\u305f\n\n\n\ndef main():\n\n    N,K = map(int, input().split())\n    X = []\n    Y = []\n    Z = []\n    spot = []\n    for i in range(N):\n        sp = list(map(int, input().split()))\n        X.append(sp[0])\n        X.append(sp[3])\n        Y.append(sp[1])\n        Y.append(sp[4])\n        Z.append(sp[2])\n        Z.append(sp[5])\n        spot.append(sp)\n    \n    X = list(set(X))\n    Y = list(set(Y))\n    Z = list(set(Z))\n    X.sort()\n    Y.sort()\n    Z.sort()\n    field = [[[0]*len(X) for _ in range(len(Y))] for _ in range(len(Z))]\n\n    for x1,y1,d1,x2,y2,d2 in spot:\n        for z in range(len(Z)):\n            for y in range(len(Y)):\n                for x in range(len(X)):\n                    if (x1 < X[x] <= x2) and (y1 < Y[y] <= y2) and (d1 < Z[z] <= d2):\n                        field[z][y][x] += 1\n    \n    ans = 0\n    for z in range(len(Z)):\n        for y in range(len(Y)):\n            for x in range(len(X)):\n                if field[z][y][x] >= K:\n                    ans += (X[x]-X[x-1])*(Y[y]-Y[y-1])*(Z[z]-Z[z-1])\n    \n    print(ans)\n\n\nif __name__ == '__main__':\n    main()\n\n", "N, K = map(int, input().split())\n\ndata = [list(map(int, input().split())) for _ in range(N)]\ns_x = set()\ns_y = set()\ns_d = set()\nfor x1, y1, d1, x2, y2, d2 in data:\n    s_x.add(x1)\n    s_x.add(x1 + 1)\n    s_x.add(x2)\n    s_x.add(x2 + 1)\n    s_y.add(y1)\n    s_y.add(y1 + 1)\n    s_y.add(y2)\n    s_y.add(y2 + 1)\n    s_d.add(d1)\n    s_d.add(d1 + 1)\n    s_d.add(d2)\n    s_d.add(d2 + 1)\n\ns_x = sorted(s_x)\ns_y = sorted(s_y)\ns_d = sorted(s_d)\nd_x = {v: i for i, v in enumerate(s_x)}\nd_y = {v: i for i, v in enumerate(s_y)}\nd_d = {v: i for i, v in enumerate(s_d)}\n\nf = [[[0]* len(s_d) for _ in range(len(s_y))] for _ in range(len(s_x))]\nfor x1, y1, d1, x2, y2, d2 in data:\n    f[d_x[x1]][d_y[y1]][d_d[d1]] += 1\n    f[d_x[x1]][d_y[y1]][d_d[d2]] -= 1\n    f[d_x[x1]][d_y[y2]][d_d[d1]] -= 1\n    f[d_x[x1]][d_y[y2]][d_d[d2]] += 1\n    f[d_x[x2]][d_y[y1]][d_d[d1]] -= 1\n    f[d_x[x2]][d_y[y1]][d_d[d2]] += 1\n    f[d_x[x2]][d_y[y2]][d_d[d1]] += 1\n    f[d_x[x2]][d_y[y2]][d_d[d2]] -= 1\n\nfor i in range(len(s_x)):\n    for j in range(len(s_y)):\n        for k in range(len(s_d) - 1):\n            f[i][j][k + 1] += f[i][j][k]\n\nfor i in range(len(s_x)):\n    for j in range(len(s_y) - 1):\n        for k in range(len(s_d)):\n            f[i][j + 1][k] += f[i][j][k]\n\nfor i in range(len(s_x) - 1):\n    for j in range(len(s_y)):\n        for k in range(len(s_d)):\n            f[i + 1][j][k] += f[i][j][k]\n\nans = 0\nfor i in range(len(s_x)):\n    for j in range(len(s_y)):\n        for k in range(len(s_d)):\n            if f[i][j][k] >= K:\n                ans += (s_x[i + 1] - s_x[i]) * (s_y[j + 1] - s_y[j]) * (s_d[k + 1] - s_d[k])\n\nprint(ans)\n\n", "import sys\nfrom bisect import bisect_left, bisect_right\n\ninput = lambda: sys.stdin.buffer.readline()\nstrinput = lambda: sys.stdin.readline()[:-1]\nsys.setrecursionlimit(10**7)\n\nL = 10**6+10\n\ndef solve():\n    n, K = map(int, input().split())\n    x, y, d = [None] * n, [None] * n, [None] * n\n\n    for i in range(n):\n        x1, y1, d1, x2, y2, d2 = map(int, input().split())\n        x[i] = x1, x2\n        y[i] = y1, y2\n        d[i] = d1, d2\n    W, xs, x = compress(L, x)\n    H, ys, y = compress(L, y)\n    D, ds, d = compress(L, d)\n\n    s = [[[0] * D for _ in range(H)] for _ in range(W)]\n    for i in range(n):\n        x1, x2 = x[i]\n        y1, y2 = y[i]\n        d1, d2 = d[i]\n        for j in range(x1, x2):\n            for k in range(y1, y2):\n                for l in range(d1, d2):\n                    s[j][k][l] += 1\n    ans = 0\n    for i in range(W-1):\n        for j in range(H-1):\n            for k in range(D-1):\n                if s[i][j][k] >= K:\n                    v = (xs[i+1]-xs[i]) * (ys[j+1]-ys[j]) * (ds[k+1]-ds[k])\n                    ans += v\n    print(ans)\n    return\n\ndef compress(n, a):\n    s = []\n    for x1, x2 in a:\n        for i in range(-1, 2):\n            nx1, nx2 = x1+i, x2+i\n            if 0 <= nx1 < n: s.append(nx1)\n            if 0 <= nx2 < n: s.append(nx2)\n    s.append(0)\n    s = sorted(set(s))\n    na = [None] * len(a)\n    for i in range(len(a)):\n        na[i] = (bisect_left(s, a[i][0]), bisect_left(s, a[i][1]))\n    return len(s), s, na\n\nsolve()\n\n", "# copy\nn, k = map(int, input().split())\nplst = []\nxlst = []\nylst = []\ndlst = []\n\nfor _ in range(n):\n    x1, y1, d1, x2, y2, d2 = map(int, input().split())\n    plst.append((x1, y1, d1, x2, y2, d2))\n    xlst.append(x1)\n    xlst.append(x2)\n    ylst.append(y1)\n    ylst.append(y2)\n    dlst.append(d1)\n    dlst.append(d2)\n\nxlst = list(set(xlst))\nylst = list(set(ylst))\ndlst = list(set(dlst))\n\nxlst.sort()\nylst.sort()\ndlst.sort()\n\nlx = len(xlst)\nly = len(ylst)\nld = len(dlst)\n\nxdic = dict(reversed(t) for t in enumerate(xlst))\nydic = dict(reversed(t) for t in enumerate(ylst))\nddic = dict(reversed(t) for t in enumerate(dlst))\n\nnew_map = [[[0] * ld for _ in range(ly)] for _ in range(lx)]\n\nfor p in plst:\n    x1, y1, d1, x2, y2, d2 = p\n    x1, y1, d1, x2, y2, d2 = \\\n        xdic[x1], ydic[y1], ddic[d1], xdic[x2], ydic[y2], ddic[d2]\n    for x in range(x1, x2):\n        for y in range(y1, y2):\n            for d in range(d1, d2):\n                new_map[x][y][d] += 1\n\nans = 0\nfor i in range(lx - 1):\n    xlsti = xlst[i]\n    xlsti1 = xlst[i + 1]\n    x = xdic[xlsti]\n    for j in range(ly - 1):\n        ylstj = ylst[j]\n        ylstj1 = ylst[j + 1]\n        y = ydic[ylstj]\n        for z in range(ld - 1):\n            dlstz = dlst[z]\n            dlstz1 = dlst[z + 1]\n            d = ddic[dlstz]\n            if new_map[x][y][d] >= k:\n                ans += (xlsti1 - xlsti) * (ylstj1 - ylstj) * (dlstz1 - dlstz)\nprint(ans)\n\n", "import itertools\n\ndef main():\n    input_lines = []\n    input_lines.append(input())\n    N, K = [int(x) for x in input_lines[0].split(' ')]\n    for i in range(N):\n        input_lines.append(input())\n\n    grid = [set() for i in range(3)]\n    data = []\n    for line in input_lines[1:]:\n        x1, y1, d1, x2, y2, d2 = [int(x) for x in line.split(' ')]\n        data.append((x1, y1, d1, x2, y2, d2))\n        grid[0].add(x1)\n        grid[0].add(x2)\n        grid[1].add(y1)\n        grid[1].add(y2)\n        grid[2].add(d1)\n        grid[2].add(d2)\n\n    grid = [sorted(g) for g in grid]\n    grid_index = [{x[1]:x[0] for x in enumerate(g)} for g in grid]\n    grid_len = [len(g) for g in grid]\n\n    fish_dist = [[[0 for i in range(grid_len[2])] for i in range(grid_len[1])] for i in range(grid_len[0])]\n\n    for x1, y1, d1, x2, y2, d2 in data:\n        x1_index = grid_index[0][x1]\n        x2_index = grid_index[0][x2]\n        y1_index = grid_index[1][y1]\n        y2_index = grid_index[1][y2]\n        d1_index = grid_index[2][d1]\n        d2_index = grid_index[2][d2]\n        for x_index, y_index, d_index in itertools.product( range(x1_index, x2_index), range(y1_index, y2_index), range(d1_index, d2_index) ):\n            fish_dist[x_index][y_index][d_index] += 1\n\n    volume = 0\n    for x_index, y_index, d_index in itertools.product(range(grid_len[0]), range(grid_len[1]), range(grid_len[2])):\n        if fish_dist[x_index][y_index][d_index] >= K:\n            x_begin = grid[0][x_index]\n            y_begin = grid[1][y_index]\n            d_begin = grid[2][d_index]\n            x_end = grid[0][x_index + 1]\n            y_end = grid[1][y_index + 1]\n            d_end = grid[2][d_index + 1]\n            volume += (x_end - x_begin) * (y_end - y_begin) * (d_end - d_begin)\n    print(volume)\n\nmain()\n"]

source: aizu

question:
Fish's Habitat Range (Fish)

  Problem

To the west of the Australian continent lies the vast Indian Ocean. Mr. JOI, a marine researcher, is studying the characteristics of N species of fish that inhabit the Indian Ocean.

For each species of fish, there is a defined habitat range in the shape of a rectangular prism in the sea. Fish can move to any location within their habitat range, including the boundaries, but they will never go outside their defined habitat. A point in the sea is represented by three real numbers (x, y, d): (x, y, d) represents the point at a depth d from the sea surface when looking down from above, after moving east by x and north by y from a certain reference point. The sea surface is considered to be flat.

Mr. JOI wants to know how much area is covered by the overlapping habitat ranges of at least K species of fish. Create a program to calculate the total volume of such areas.

  Input

The input consists of 1 + N lines.

The first line contains two integers N, K (1 ≤ K ≤ N ≤ 50) separated by a space. This indicates that there are N species of fish and that we want to find the volume of the area where the habitat ranges of at least K species of fish overlap.

Each of the following N lines corresponds to the i-th line (1 ≤ i ≤ N), containing six integers X_{i,1}, Y_{i,1}, D_{i,1}, X_{i,2}, Y_{i,2}, D_{i,2} (0 ≤ X_{i,1} < X_{i,2} ≤ 1000000 (= 10^{6}), 0 ≤ Y_{i,1} < Y_{i,2} ≤ 1000000 (= 10^{6}), 0 ≤ D_{i,1} < D_{i,2} ≤ 1000000 (= 10^{6})). This indicates that the habitat range of the i-th species of fish is a rectangular prism with vertices at points (X_{i,1}, Y_{i,1}, D_{i,1}), (X_{i,2}, Y_{i,1}, D_{i,1}), (X_{i,2}, Y_{i,2}, D_{i,1}), (X_{i,1}, Y_{i,2}, D_{i,1}), (X_{i,1}, Y_{i,1}, D_{i,2}), (X_{i,2}, Y_{i,1}, D_{i,2}), (X_{i,2}, Y_{i,2}, D_{i,2}), (X_{i,1}, Y_{i,2}, D_{i,2}).

  Output

Output the total volume of the area where the habitat ranges of at least K species of fish overlap on one line.

  Input and Output Examples
Example Input 1

3 2
30 50 0 50 70 100
10 20 20 70 90 60
40 60 20 90 90 70

Example Output 1

49000

In Example Input 1, for instance, the point (45, 65, 65) lies within the habitat ranges of the first and third species of fish, and so it meets the condition. On the other hand, the point (25, 35, 45) is only within the habitat range of the second species of fish and does not meet the condition. The habitat ranges of the fish are illustrated in the figure below, with point O representing the reference point on the sea surface.

![image](1.png)

Example Input 2

1 1
0 0 0 1000000 1000000 1000000

Example Output 2

1000000000000000000

The problem statement and the data used for automatic judgments are created and published by the Japanese Committee for Information Olympiad.

data_split: test


difficulty: HARD

raw_tags: ['Algorithms - Constructive Algorithms']

source: hacker rank

question:
Consider an array, $A=a_0,a_1,...,a_{n-1}$, of $n$ integers. We define the following terms:

Subsequence

A subsequence of $\mbox{A}$

is an array that's derived by removing zero or more elements from $\mbox{A}$ without changing the order of the remaining elements. Note that a subsequence may have zero elements, and this is called the empty subsequence.

Strictly Increasing Subsequence

A non-empty subsequence is strictly increasing if every element of the subsequence is larger than the previous element.

Subarray

A subarray of $\mbox{A}$ is an array consisting of a contiguous block of $\mbox{A}$'s elements in the inclusive range from index $\boldsymbol{l}$ to index $\textbf{r}$. Any subarray of $\mbox{A}$ can be denoted by $A[l,r]=a_l,a_{l+1},...,a_r$.

The diagram below shows all possible subsequences and subarrays of $A=[2,1,3]$:![image](1.png)

We define the following functions:

$sum(l,r)=a_l+a_{l+1}+…+a_r$
$inc(l,r)$ = the maximum sum of some strictly increasing subsequence in subarray $A[l,r]$
$f(l,r)=sum(l,r)-inc(l,r)$

We define the goodness, $\mathrm{~g~}$, of array $\mbox{A}$ to be:

$g=max\ f(l,r)\ \text{for }\ 0\leq l\leq r\lt n$

In other words, $\mathrm{~g~}$ is the maximum possible value of $f(l,r)$ for all possible subarrays of array $\mbox{A}$.

Let $m$ be the length of the smallest subarray such that $f(l,r)=g$. Given $\mbox{A}$, find the value of $\mathrm{~g~}$ as well as the number of subarrays such that $r-l+1=m$ and $f(l,r)=g$, then print these respective answers as space-separated integers on a single line.

Input Format

The first line contains an integer, $n$, denoting number of elements in array $\mbox{A}$.

The second line contains $n$ space-separated integers describing the respective values of $a_0,a_1,\ldots,a_{n-1}$.

Constraints

$1\leq n\leq2\cdot10^5$
$-40\leq a_i\leq40$

Subtasks

For the $20\%$ of the maximum score:

$1\leq n\leq2000$

$-10\leq a_i\leq10$

For the $\textbf{60\%}$ of the maximum score:

$1\leq n\leq10^5$

$-12\leq a_i\leq12$

Output Format

Print two space-seperated integers describing the respective values of $\mathrm{~g~}$ and the number of subarrays satisfying $r-l+1=m$ and $f(l,r)=g$.

Sample Input 0
3
2 3 1

Sample Output 0
1 1

Explanation 0

The figure below shows how to calculate $\mathrm{~g~}$:

$m$ is the length of the smallest subarray satisfying $f(l,r)$. From the table, we can see that $m=2$. There is only one subarray of length $2$ such that $f(l,r)=g=1$.

data_split: test


Cubic Eight-Puzzle

source: ACM International Collegiate Programming Contest, Asia Regional 2006, Japan

raw_problem:
Problem C: Cubic Eight-Puzzle

Let's play a puzzle using eight cubes placed on a 3 × 3 board leaving one empty square.

Faces of cubes are painted with three colors. As a puzzle step, you can roll one of the cubes to
the adjacent empty square. Your goal is to make the specified color pattern visible from above
by a number of such steps.

The rules of this puzzle are as follows.

Coloring of Cubes: All the cubes are colored in the same way as shown in Figure 3.
The opposite faces have the same color.

Figure 3: Coloring of a cube

Initial Board State: Eight cubes are placed on the 3 × 3 board leaving one empty square.
All the cubes have the same orientation as shown in Figure 4. As shown in the figure,
squares on the board are given x and y coordinates, (1, 1), (1, 2), .. ., and (3, 3). The
position of the initially empty square may vary.

Figure 4: Initial board state

Rolling Cubes: At each step, we can choose one of the cubes adjacent to the empty square and roll it into the empty square, leaving the original position empty. Figure 5
shows an example.

Figure 5: Rolling a cube

Goal: The goal of this puzzle is to arrange the cubes so that their top faces form the
specified color pattern by a number of cube rolling steps described above.

Your task is to write a program that finds the minimum number of steps required to make the
specified color pattern from the given initial state.

Input

The input is a sequence of datasets. The end of the input is indicated by a line containing two
zeros separated by a space. The number of datasets is less than 16. Each dataset is formatted
as follows.

        x y
        F11 F21 F31
        F12 F22 F32
        F13 F23 F33

The first line contains two integers x and y separated by a space, indicating the position (x, y)
of the initially empty square. The values of x and y are 1, 2, or 3.

The following three lines specify the color pattern to make. Each line contains three characters
F1j, F2j, and F3j, separated by a space. Character Fij indicates the top color of the cube, if any, at position (i, j) as follows:

       B: Blue
       W: White
       R: Red
       E: the square is Empty.

There is exactly one 'E' character in each dataset.

Output

For each dataset, output the minimum number of steps to achieve the goal, when the goal can
be reached within 30 steps. Otherwise, output "-1" for the dataset.

Sample Input

1 2
W W W
E W W
W W W
2 1
R B W
R W W
E W W
3 3
W B W
B R E
R B R
3 3
B W R
B W R
B E R
2 1
B B B
B R B
B R E
1 1
R R R
W W W
R R E
2 1
R R R
B W B
R R E
3 2
R R R
W E W
R R R
0 0

Output for the Sample Input

0
3
13
23
29
30
-1
-1

input_output: {"inputs": ["2 2\nB E B\nB B B\nB B B\n2 3\nW B W\nW R W\nE W R\n2 2\nW W W\nE B W\nW W W\n3 2\nR R R\nE W R\nR R R\n2 1\nR B E\nB R W\nW W W\n1 3\nB W B\nB W B\nB E B\n1 2\nB W W\nR E W\nB R W\n2 2\nW W W\nW E W\nW W W\n2 3\nB R B\nB E B\nB R B\n2 2\nW E R\nR R R\nR B B\n2 1\nB R B\nR E B\nR W B\n3 3\nB R B\nB W B\nB W E\n1 1\nR W B\nR W R\nW E R\n1 3\nE R R\nB B B\nR R R\n3 2\nR B W\nR W E\nB W W\n0 0\n"], "outputs": ["-1\n17\n1\n30\n5\n-1\n7\n0\n-1\n9\n29\n30\n11\n26\n8\n"]}

solutions: ["import sys\nfrom collections import deque\nfrom itertools import product\nreadline = sys.stdin.readline\nwrite = sys.stdout.write\n\nnxt = [\n    [[3], [1]],\n    [[4], [0, 2]],\n    [[5], [1]],\n    [[0, 6], [4]],\n    [[1, 7], [3, 5]],\n    [[2, 8], [4]],\n    [[3], [7]],\n    [[4], [6, 8]],\n    [[5], [7]],\n]\n\nroll = [\n    [1, 0, 3, 2, 5, 4],\n    [5, 2, 1, 4, 3, 0],\n]\n\nWRB = \"WRB\"\nfront = [0, 1, 2, 0, 1, 2, 3]\n\ndef calc(state_l, s, lim):\n    res = {}\n    dist = {state0: 0 for state0 in state_l}\n    que = deque([(state0, s) for state0 in state_l])\n    tmp = [0]*9\n\n    roll0, roll1 = roll\n\n    while que:\n        state, a = que.popleft()\n        d = dist[state]\n\n        key = tuple(map(front.__getitem__, state))\n        if key not in res:\n            res[key] = d\n\n        if d == lim:\n            continue\n\n        tmp[:] = state\n        for b in nxt[a][0]:\n            tmp[a] = roll0[tmp[b]]\n            tmp[b] = 6\n            key = tuple(tmp)\n            if key not in dist:\n                dist[key] = d+1\n                que.append((key, b))\n            tmp[b] = state[b]\n        for b in nxt[a][1]:\n            tmp[a] = roll1[tmp[b]]\n            tmp[b] = 6\n            key = tuple(tmp)\n            if key not in dist:\n                dist[key] = d+1\n                que.append((key, b))\n            tmp[b] = state[b]\n    return res, dist\n\ndef solve():\n    ss = []\n    for i in range(3):\n        for j in range(3):\n            s = i*3+j\n            state0 = tuple(0 if s != k else 6 for k in range(9))\n            ss.append(calc([state0], s, 20))\n    while 1:\n        x, y = map(int, readline().split())\n        if x == y == 0:\n            break\n        x -= 1; y -= 1\n        F = [readline().split() for i in range(3)]\n        k = -1\n        s = []\n        for i in range(3):\n            for j in range(3):\n                if F[i][j] == \"E\":\n                    s.append(3)\n                    k = 3*i+j\n                else:\n                    s.append(WRB.index(F[i][j]))\n        key = tuple(s)\n        s0, d0 = ss[3*y+x]\n        if key in s0:\n            write(\"%d\\n\" % s0[key])\n            continue\n\n        state_l = []\n        for ps in product([0, 3], repeat=8):\n            cur = 0\n            state = []\n            for e in s:\n                if e == 3:\n                    state.append(6)\n                else:\n                    state.append(e + ps[cur])\n                    cur += 1\n            state_l.append(tuple(state))\n        s1, d1 = calc(state_l, k, 10)\n        ans = 31\n        for key in d1.keys():\n            if key in d0 and d0[key] + d1[key] < ans:\n                ans = d0[key] + d1[key]\n        if ans < 31:\n            write(\"%d\\n\" % ans)\n        else:\n            write(\"-1\\n\")\nsolve()\n"]

source: aizu

question:
Problem C: Cubic Eight-Puzzle

Let's play a puzzle using eight cubes placed on a 3 × 3 board leaving one empty square.

Faces of cubes are painted with three colors. As a puzzle step, you can roll one of the cubes to
the adjacent empty square. Your goal is to make the specified color pattern visible from above
by a number of such steps.

The rules of this puzzle are as follows.

-
Coloring of Cubes: All the cubes are colored in the same way as shown in Figure 3.
The opposite faces have the same color.

![image](1.png)
Figure 3: Coloring of a cube

-
Initial Board State: Eight cubes are placed on the 3 × 3 board leaving one empty square.
All the cubes have the same orientation as shown in Figure 4. As shown in the figure,
squares on the board are given x and y coordinates, (1, 1), (1, 2), .. ., and (3, 3). The
position of the initially empty square may vary.

![image](2.png)
Figure 4: Initial board state

-
Rolling Cubes: At each step, we can choose one of the cubes adjacent to the empty square and roll it into the empty square, leaving the original position empty. Figure 5
shows an example.

![image](3.png)
Figure 5: Rolling a cube

-
Goal: The goal of this puzzle is to arrange the cubes so that their top faces form the
specified color pattern by a number of cube rolling steps described above.

Your task is to write a program that finds the minimum number of steps required to make the
specified color pattern from the given initial state.

Input

The input is a sequence of datasets. The end of the input is indicated by a line containing two
zeros separated by a space. The number of datasets is less than 16. Each dataset is formatted
as follows.

_{11} _{21} _{31}

_{12} _{22} _{32}

_{13} _{23} _{33}

The first line contains two integers x and y separated by a space, indicating the position (x, y)
of the initially empty square. The values of x and y are 1, 2, or 3.

The following three lines specify the color pattern to make. Each line contains three characters
F_{1j}, F_{2j}, and F_{3j}, separated by a space. Character F_{ij} indicates the top color of the cube, if any, at position (i, j) as follows:

       B: Blue
       W: White
       R: Red
       E: the square is Empty.

There is exactly one 'E' character in each dataset.

Output

For each dataset, output the minimum number of steps to achieve the goal, when the goal can
be reached within 30 steps. Otherwise, output "-1" for the dataset.

Sample Input

1 2
W W W
E W W
W W W
2 1
R B W
R W W
E W W
3 3
W B W
B R E
R B R
3 3
B W R
B W R
B E R
2 1
B B B
B R B
B R E
1 1
R R R
W W W
R R E
2 1
R R R
B W B
R R E
3 2
R R R
W E W
R R R
0 0

Output for the Sample Input

0
3
13
23
29
30
-1
-1

image_tags:
3D Geometry
3D Geometry
3D Geometry

data_split: test