๐Ÿ”™ Back to Top

Sat May 2 02:01:36 JST 2015

ๅ†™็œŸใ‹ใ‚‰ๆ‰‹ๆ›ธใใฃใฝใ„ๆผซ็”ปใฎ็”Ÿๆˆ

ppm(P3)ใ‹ใ‚‰ppm(P2)ใธใฎๅค‰ๆ›ใ‚’ใ™ใ‚‹

#include <bits/stdc++.h>
using namespace std;

#define rep(i,n) for(int i=0;i<(n);++i)
#define loop for(;;)
#define trace(var) cerr<<">>> "<<#var<<" = "<<var<<endl;
#define inf (1e9)

template<class S, class T> inline
ostream& operator<<(ostream&os, pair<S,T> p) {
  os << '(' << p.first << ", " << p.second << ')';
  return os;
}

template<class T> inline
ostream& operator<<(ostream&os, vector<T> v) {
  if (v.size() == 0) {
    os << "(empty)";
    return os;
  }
  os << v[0];
  for (int i=1, len=v.size(); i<len; ++i) os << ' ' << v[i];
  return os;
}

template<class T> inline
istream& operator>>(istream&is, vector<T>&v) {
  rep (i, v.size()) is >> v[i];
  return is;
}

template<class S, class T, class U> inline
ostream& operator<<(ostream&os, tuple<S, T, U> t) {
  return os << '(' << get<0>(t) << ", " << get<1>(t)
    << ", " << get<2>(t) << ')';
}

using vi = vector<int>;
using vvi = vector<vi>;

void display(string format, int w, int h, int c, vvi gray) {
  cout << format << endl;
  cout << w << ' ' << h << endl;
  cout << c << endl;
  rep (i, h) {
    rep (j, w) {
      cout << min(c, max(0, gray[i][j]));
      cout << (j%15==14 ? '\n' : ' ');
    }
    cout << endl;
  }
}

int main(int argc, char*argv[]) {
  string format; cin >> format;
  int w, h; cin >> w >> h;
  int area = w * h;
  int c; cin >> c;
  vector<vvi> cols(3, vvi(h, vi(w)));
  rep (i, h) {
    rep (j, w) {
      cin
        >> cols[0][i][j]
        >> cols[1][i][j]
        >> cols[2][i][j];
      rep (k, 3) cols[k][i][j] = c - cols[k][i][j];
    }
  }

  // embossing
  const int D = 4;
  rep (k, 3) {
    rep (i, h) {
      rep (j, w) {
        int max_c = 0;
        int min_c = c;
        for (int dx = -D; dx <= D; ++dx) {
          for (int dy = -D; dy <= D; ++dy) {
            int x = i + dx;
            int y = j + dy;
            if (x < 0 or y < 0 or x >= h or y >= w) continue;
            max_c = max(max_c, cols[k][x][y]);
            min_c = min(min_c, cols[k][x][y]);
          }
        }
        int mid_c = (max_c + min_c) / 2;
        for (int dx = -D; dx <= D; ++dx) {
          for (int dy = -D; dy <= D; ++dy) {
            int x = i + dx;
            int y = j + dy;
            if (x < 0 or y < 0 or x >= h or y >= w) continue;
            int c = cols[k][x][y];
            cols[k][x][y] = c < mid_c ? 0 : c;
          }
        }
      } } }
  cerr << "embossing: done" << endl;

  vvi gray(h, vi(w, c));

  rep (k, 3) { // random walk for-each color
    int x = rand() % h,
        y = rand() % w;
    rep (_, area/2) {
      const int D = 10;
      int dx, dy,
          x2, y2;
      rep (__, 10) {
        dx = rand() % (2*D+1) - D;
        dy = rand() % (2*D+1) - D;
        x2 = max(0, min(h - 1, x + dx));
        y2 = max(0, min(w - 1, y + dy));
        if (x == x2 and y == y2) continue;
        if (cols[k][x2][y2] > rand()%c) break;
      }
      { // draw a line
        int weight = (cols[k][x2][y2] + cols[k][x][y]) / 10;
        for (int d = 0; d <= D; ++d) {
          int xi = x + d * (x2 - x) / D;
          int yi = y + d * (y2 - y) / D;
          gray[xi][yi] -= weight;
          cols[k][x][y] -= weight;
        }
      }
      x = x2; y = y2;
    }
  }

  display("P2", w, h, c, gray);

  return 0;
}

้ญš้‡ฃใ‚Šใ€ๅŒๆƒ…ใ€่ฟทๅญใ”ใฃใ“

้ญš้‡ฃใ‚Šใจใ„ใ†่กŒ็‚บใ‚’็›ฎใฎๅฝ“ใŸใ‚Šใซใ—ใŸๆ™‚
้ญšใฏไฝ•ใฎใŸใ‚ใซ็”Ÿใใฆใ„ใ‚‹ใฎใ ใ‚ใ†ใจ็œŸๅ‰ฃใซ่€ƒใˆใŸใฎใ‚’่ฆšใˆใฆใ„ใ‚‹
ใ‚ใ‚Œใฏใ‚Œใฃใใจใ—ใŸใ€ๅจฏๆฅฝใจใ—ใฆใฎใ€็‹ฉ็ŒŸใ 
ไบบ้–“ใฎ้ƒฝๅˆใฎใŸใ‚ใซ้ฃผใ‚ใ‚Œใ‚‹้ญšใฏๆฑบใ—ใฆๅฏๆ„›ใŒใ‚‰ใ‚Œใ‚‹็‚บใฎใ‚‚ใฎใ˜ใ‚ƒใชใ„
ใกใ‚‡ใฃใจ่€ƒใˆใ‚’่ปขๆ›ใ™ใ‚‹ใจใ€ๆฐดๆ—้คจใฎ้ญšใจใ„ใ†ใฎใ‚‚ใ€ใตใคใ†ใ€ๅฏๆ„›ใŒใ‚‰ใ‚Œใ‚‹ใ‚‚ใฎใงใฏใชใ„ใ ใ‚ใ†

็ฅžไฟ็”บใ‹ใ‚‰ใ€ๆ—ฅไป˜ใŒไปฃใ‚ใ‚‹ๅ‰ใฎๆ˜จๆ—ฅใฏๆ˜ ็”ปใฎๆ—ฅใงใ‚ใฃใŸใฎใงใ€ ๆ˜ ็”ปใ‚’่ฆ‹ใ‚‹ใŸใ‚ใซๆฑ ่ข‹ใซ่กŒใใ“ใจใซใ—ใŸใ€‚ ใ“ใฎ้ ƒใพใŸๆš–ใ‹ใชใฎใงใ€็งใฎ่ถณใฏ่‡ช่ปข่ปŠใงใ‚ใฃใŸใ€‚ ใ„ใคใ‚‚่ตฐใ‚‹้“ใ ใจใ€็ฅžไฟ็”บใ‹ใ‚‰ใพใฃใ™ใใซๆ—ง็™ฝๅฑฑ้€šใ‚ŠใงๅŒ—ใซ่ตฐใ‚Šใ€ ๅƒ็Ÿณใฎใ‚ใŸใ‚Šใงใ€ไธๅฟ้€šใ‚ŠใงไปŠๅบฆใฏใพใฃใ™ใ่ฅฟใซๅ‘ใ‹ใฃใฆๆ˜ฅๆ—ฅ้€šใ‚Šใซใถใคใ‹ใ‚‹ใพใง่ตฐใ‚‹ใ€‚ ไปŠๅบฆใฏใใ“ใ‹ใ‚‰ๅฐ‘ใ—ๅŒ—ใซ่ตฐใ‚‹ใจๆฑ ่ข‹ใงใ‚ใ‚‹ใ€‚ ใฉใ‚“ใช้“่ทฏใŒๅœจใ‚‹ใ‹ใซใ‚‚ใ‚ˆใ‚‹ใŒใ€ไธ€่ˆฌ็š„ใซ่จ€ใฃใฆใ€ใ“ใ‚Œใฏ็„ก้ง„ใฎใ‚ใ‚‹่ตฐ่ทฏใงใ‚ใ‚ใ†ใ€‚ ๆ–œใ‚ใซไธ€็›ด็ทšใซ่กŒใ‘ใ‚‹ๆ–นใŒ่ฟ‘้“ใงใ‚ใ‚‹ใ€‚ ใใ†ใ„ใ†ใ‚ใ‘ใงไปŠๆ—ฅใฏใ€่ฟ‘้“ใ‚’็›ฎๆŒ‡ใ—ใฆใ€ไปŠใพใง่ตฐใฃใŸใ“ใจใ‚‚ใชใ„้“ใ ใ‘ใ‚’่ตฐใฃใฆๆฑ ่ข‹ใพใง่กŒใใ“ใจใซใ—ใŸใ€‚ ใฉใ†ใ›่ฆ‹็Ÿฅใ‚‰ใฌ้“ใงใ‚ใ‚‹ใ€‚ ่ฆ‹็ŸฅใฃใŸ้“ใ‚’ใšใ„ใšใ„่ตฐใ‚‹ใปใ†ใŒ่ฟ‘ใ„ใซๆฑบใพใฃใฆใ„ใ‚‹ใฎใงใ‚ใ‚‹ใŒใ€ ใ“ใ‚Œใฏใพใ‚ใ€ ไธ€ใคใฎ้Šใณใ ใ€‚ ่‡ชๅˆ†ใ‹ใ‚‰ใ™ใ™ใ‚“ใง่ฟทๅญใซใชใ‚‹ใ€‚ ๅญไพ›ใ‚ˆใใ‚„ใ‚‹ๆŽขๆคœใ”ใฃใ“ใ ใ€‚ ่กŒใใฏๅคช้™ฝใŒๅ‡บใฆใ„ใŸใ‹ใ‚‰็ฐกๅ˜ใ ใฃใŸใ€‚ ๆฏ”่ผƒ็š„็ฐกๅ˜ใซใ€ๆ˜ฅๆ—ฅ้€šใ‚Šใซใถใคใ‹ใ‚‹ใ“ใจใŒใงใใŸใ€‚ ็ฅžไฟ็”บใ‹ใ‚‰ใ€ไธ€ๆ—ฆใ€้ฃฏ็”ฐๆฉ‹ใพใง่ตฐใฃใฆใ€ใใ“ใ‹ใ‚‰ๅคงไฝ“็œŸๅŒ—ใ‚’็›ฎๆŒ‡ใ—ใŸใ€‚ ๅฐ็Ÿณๅทใ‚’้€šใ‚Šใฌใ‘ใ€่Œ—่ท่ฐทใจใ„ใ†ๆ–‡ๅญ—ใ‚’็›ฎๆŒ‡ใ—ใฆ่ตฐใ‚‹ใจใ€ๆ˜ฅๆ—ฅ้€šใ‚Šใฏ้šๅˆ†ๆ•ดๅ‚™ใ•ใ‚Œใฆใ„ใŸใ€‚ ้€”ไธญใง้€šใฃใŸๅฐ็Ÿณๅทๅ››ไธ็›ฎใฏไปๆ•™ใฎๆŸ“ใฟ้€šใฃใŸ็”บใงใ‚ใ‚‹ใ‚‰ใ—ใใ€ใใ†ใ„ใฃใŸๆ–ฝ่จญใ‚„ๅนผ็จšๅœ’ใŒใ‚ˆใ่ฆ‹ๅ—ใ‘ใ‚‰ใ‚ŒใŸใ€‚ ๅญใฉใ‚‚ใŸใกใฏๅ…ฌ้“ใฎไธŠใงใ‚ญใƒฃใƒƒใƒใƒœใƒผใƒซใ‚’ใ—ใ€ ๆ’ญ็ฃจๅ‚ใ•ใใ‚‰ไธฆๆœจใฏใ€ๆฑไบฌใฎ็œŸใ‚“ไธญใจใ—ใฆใฏ็ใ—ใ„ใใ‚‰ใ„ใฎ็ท‘่‰ฒใ‚’็งใซ่ฆ‹ใ›ใฆใใ‚Œใฆใ€ ๅคงๅค‰ใฎใฉใ‹ใงๅนณๅ’Œใชๅฐ่ฑกใงใ‚ใฃใŸใ€‚

ใฉใ“ใ‚’ใฉใ†่ตฐใฃใฆใ‚‚ใ€ๅฐ็Ÿณๅทๆค็‰ฉๅœ’ใจใถใคใ‹ใฃใฆๅคงๅค‰้‚ช้ญ”ใ ใฃใŸใ€‚ ๆฑ ่ข‹ใ‹ใ‚‰ใฎๅธฐใ‚Šใ‚‚็Ÿฅใ‚‰ใชใ„้“ใ‚’ใงใใ‚‹ใ ใ‘่ตฐใ‚‹ใ“ใจใซใ—ใŸใ€‚ ใชใ‚“ใ›็งใฏ็พไปฃไบบใ‚‰ใ—ใ‹ใ‚‰ใฌใ‚นใƒžใƒผใƒˆใƒ•ใ‚ฉใƒณใชใ‚“ใฆใ‚‚ใฎใ‚’ๆŒใŸใชใ„ใฎใงใ€ ๆœฌๅฝ“ใซ่ฟทๅญใซใชใฃใŸใ‚‰ๆœฌๅฝ“ใซใ€ใงใ‚ใ‚‹ใ€‚ ใ—ใ‹ใ—ใพใ‚ใ€ๆ€ใˆใฐใ€ ใ‚ใ–ใจใกใ‚‡ใฃใจ่ฟทๅญใซใชใฃใฆใฟใ‚‹่ถฃๅ‘ณใฏๅคงๆ˜”ใ‹ใ‚‰ใ ใฃใŸใ€‚ ใ“ใ‚Œใฏ่จ€ใฃใฆใฟใ‚Œใฐใ€ๅนณๅ‡กใชๆ—ฅๅธธใซใกใ‚‡ใฃใจใ—ใŸใ‚นใƒชใƒซใ‚’ๅŠ ใˆใ‚‹ใ“ใจใงใ‚ใ‚‹ใ€‚ ใ‚นใƒžใƒผใƒˆใƒ•ใ‚ฉใƒณใŒใชใใฆใ‚‚ใ€้“่ทฏๆจ™่ญ˜ใ‚’ใ‚ˆใ่ฆ‹ใฆใ„ใ‚Œใฐๅคงไฝ“่‡ชๅˆ†ใŒใฉใ“ใซใ„ใ‚‹ใ‹ใ‚ใ‹ใ‚‹ใ—ใ€ ่‡ชๅˆ†ใŒ้ซ˜ๆ ก็”Ÿใฎ้ ƒใฏใ—ใ‚‡ใฃใกใ‚…ใ†ใ€ไบค็•ชใซ้“ใ‚’่จชใญใฆใ€้ง…ใฎๅ ดๆ‰€ใ‚’ๅฐ‹ใญใŸใ‚‰ใ™ใ่ฃใ ใฃใŸใชใ‚“ใฆใ“ใจใŒใ‚ใ‚‹ใ€‚ ่‡ชๅˆ†ใŒ่กŒใๅฟ…่ฆใฎใ‚ใ‚‹ๆ•ฐใ‚ซๆ‰€ใ€ๅฎถใ€ๅคงๅญฆใ€ๆœฌๅฑ‹ใ•ใ‚“ใ€ๆ˜ ็”ป้คจใ€ใใ‚Œใ‚‰ใ‚’ใคใชใใ€ใŸใ‹ใ ใ‹ๆ•ฐๆœฌใฎ้“ใ ใ‘ใ‚’่ตฐใ‚‹ใฎใŒๆ—ฅๅธธใ ใจ่€ƒใˆใฆใ„ใ‚‹ใจใ“ใ‚ใซ็”ฑๆฅใ™ใ‚‹ใฎใงใฏใชใ„ใ‹ใ€‚ ใคใพใ‚Šใ€ ๆ—…่กŒใซ่กŒใใชใ‚“ใฆใ€ใใ‚“ใชใ“ใจใ™ใ‚‹ไบบใŒๆœฌๅฝ“ใซใ„ใ‚‹ใชใ‚“ใฆใ€ๆ€ใ‚ใชใ‹ใฃใŸใ€‚ ใ„ใ‚„ใ€ใใ‚Šใ‚ƒใ„ใ‚‹ใ‚“ใ ใ‚ใ†ใ‘ใฉใ•ใ€ ๆ—…่กŒไผš็คพใฃใฆใ‚ใ‚‹ใ—ใ•ใ€‚ ใงใ‚‚ใ ใ‹ใ‚‰ใฃใฆใ€ ใ‚ใ–ใ‚ใ–่‡ชๅˆ†ใฎใŠ้‡‘ใ‚’ๆ‰•ใฃใฆใ ใ‚ˆ๏ผŸ ๆฅฝใ—ใ„ใ‹ใฉใ†ใ‹ใ‚‚ๅฎšใ‹ใ˜ใ‚ƒใชใ„ใŸใ ใฎ็งปๅ‹•ใ ใ‚ˆใ€‚ ็ด”็ฒ‹ใซๆ—…่กŒใ‚’็›ฎ็š„ใซใ—ใŸๆ—…่กŒใชใ‚“ใฆใ€่‡ชๅˆ†ใŒใ™ใ‚‹ใ“ใจใŒใ€ใ‚ใ‚‹ใ‹ใ—ใ‚‰

ใƒšใƒƒใƒˆใ‚ทใƒงใƒƒใƒ—ใซใŠใ„ใฆใ€ ๅคงใพใ‹ใซใ„ใˆใฐใ€็Šฌใจ็Œซใจใ€ใใฎไป–๏ผˆ้ญšใจใ‹๏ผ‰ใŒๆ‰ฑใ‚ใ‚Œใ‚‹ใ€‚ ็Šฌใจ็ŒซใŒไธปๅฝนใ ใ€‚ ใใฎไป–ใ€ใ™ใชใ‚ใก้ญš้กžใชใ‚“ใ‹ใฏใ€ๅฏๆ„›ใŒใ‚‰ใ‚Œใชใ„ใ€‚ ๅฎขใซใ€ใงใฏใชใใฆใ€ๅบ—ๅ“กใซใ€ใ ใ€‚ ๅฐ‘ใชใ‹ใ‚‰ใšใ€ไธ€้ƒจใฎๅฎขใฏใ€็†ฑๅธฏ้ญšใ‚„ใ‚‰ใซ็†ฑๅฟƒใ ใ€‚ ๆˆ‘ใ€…ใ‚ˆใ‚Š็†ฑๅฟƒใ ใ€‚ ใ ใฃใฆใ€ใใ‚“ใชใŸใ ใฎๆฐด่‰ใ‚’ใ‚ใ–ใ‚ใ–่ฒทใฃใฆใ„ใใ‚“ใ ใ‚‚ใ‚“ใ€‚ ใ‚ใ‹ใ‚ใงใ‚‚ๅ…ฅใ‚ŒใฆใŠใ‘ใฐใ„ใ„ใฎใซใ€‚ ๅคงๅ‹ขใฎ็พคใ‚Œใ‚’ใชใ™้ญšใฏใ€ ๆฐดๆ—้คจใซใŠใ„ใฆใฏใ€ๅฎขใซใ‚‚ๆฐดๆ—้คจใฎไบบใซใ‚‚ๅฏๆ„›ใŒใ‚‰ใ‚Œใชใ„ใ‚“ใ ใ‚ใ†ใชใ‚ใ€‚

ใ‚ฟใ‚คใƒซใ‚’ใ‚นใƒฉใ‚คใƒ‰ใ™ใ‚‹ใƒ‘ใ‚บใƒซ

ใ—ใ‚‡ใ†ใ‚‚ใชใ„ใ“ใจใ‚’ใ—ใฆใพใ—ใŸใ€‚
Rubpix ใชใ‚‹Flash่ฃฝใƒ‘ใ‚บใƒซใ‚’ใ‚„ใฃใฆใฆใ€ใ ใ‚“ใ ใ‚“่พ›ใใชใฃใฆใใŸใฎใงใ€ ่งฃใใƒ—ใƒญใ‚ฐใƒฉใƒ ใ‚’ๆ›ธใไฝœๆˆฆใซๅค‰ๆ›ดใ—ใŸ

  1. \(n \times n\) ใซ่‰ฒใฎใคใ„ใŸใ‚ฟใ‚คใƒซใŒไธฆใ‚“ใงใ„ใ‚‹
  2. ่กŒใพใŸใฏๅˆ—ใซใคใ„ใฆ (ไธŠไธ‹ๅทฆๅณใซไธ€ใค) ใ‚ทใƒ•ใƒˆใ™ใ‚‹ๆ“ไฝœใŒ่จฑใ•ใ‚Œใฆใ„ใ‚‹
  3. ็›ฎๆจ™ใฎ่‰ฒใฎ้…็ฝฎ (\(n \times n\)) ใซไธ€่‡ดใ•ใ›ใŸใ‚‰ใ‚ดใƒผใƒซ

ใฏใ˜ใ‚ใฏ \(3 \times 3\) ใงใ€ๅ‹˜ใงๅ‡บๆฅใ‚‹ใ‚“ใ ใ‘ใฉใ€้ฃฝใใฆใใ‚‹
ใ‚นใƒ†ใƒผใ‚ธใŒไธŠใŒใ‚‹ใ”ใจใซใ€\(n\)ใฎๆ•ฐใฏๅพใ€…ใซๅข—ใˆใ‚‹ใ‚‰ใ—ใใ€
\(4 \times 4\) ใซใชใ‚‹ใจใ‚‚ใ†ใ€ๆœฌๆ ผ็š„ใซ้›ฃใ—ใ•ใ‚’ๆ„Ÿใ˜ใฆใใ‚‹
ใพใ ็งใฏใใฎ็”ป้ขใ‚’่ฆ‹ใŸใ“ใจใŒใชใ„ใŒใ€"rubpix" ใง็”ปๅƒๆคœ็ดขใ‚’ใ™ใ‚‹ใจใ€ \(6 \times 6\) ใ‚‚ๅ‡บใฆใใ‚‹

ไปฅไธ‹ใฏ \(n \times n\) ใฎๅ ดๅˆใซใคใ„ใฆใ€ๅŒๆ–นๅ‘ๆŽข็ดขใง่งฃใใƒ—ใƒญใ‚ฐใƒฉใƒ 
\(6 \times 6\) ใงใ‚‚็พๅฎŸ็š„ใชๆ™‚้–“ใง่งฃใ‘ใ‚‹ใฎใ‹ใกใ‚‡ใฃใจ่‡ชไฟกใŒใชใ„
้ ญใฎใ„ใ„ใƒ’ใƒฅใƒผใƒชใ‚นใƒ†ใ‚ฃใƒƒใ‚ฏใ‚’ๅ…ฅใ‚Œใ‚‹ในใใ 

// you can read this source 
// also at: https://gist.github.com/cympfh/3ddc2e84211f37a81bb1
#include <bits/stdc++.h>
using namespace std;

#define rep(i,n) for(int i=0;i<(n);++i)
#define loop for(;;)
#define trace(var) cerr<<">>> "<<#var<<" = "<<var<<endl;
#define inf (1e9)

template<class S, class T> inline
ostream& operator<<(ostream&os, pair<S,T> p) {
  os << '(' << p.first << ", " << p.second << ')';
  return os;
}

template<class T> inline
ostream& operator<<(ostream&os, vector<T> v) {
  if (v.size() == 0) {
    os << "(empty)";
    return os;
  }
  os << v[0];
  for (int i=1, len=v.size(); i<len; ++i) os << ' ' << v[i];
  return os;
}

template<class T> inline
istream& operator>>(istream&is, vector<T>&v) {
  rep (i, v.size()) is >> v[i];
  return is;
}

template<class S, class T, class U> inline
ostream& operator<<(ostream&os, tuple<S, T, U> t) {
  return os << '(' << get<0>(t) << ", " << get<1>(t)
    << ", " << get<2>(t) << ')';
}

using vi = vector<char>;
using vvi = vector<vi>;

enum Dir {
  Down = 0,
  Up = 1,
  Left = 2,
  Right = 3
};

Dir invert(Dir d) {
  if (d == Down) return Up;
  if (d == Up) return Down;
  if (d == Left) return Right;
  if (d == Right) return Left;
}

struct Op {
  Dir dir; int pos;
  Op(int _pos, Dir _d) : pos(_pos), dir(_d) {}
};

inline
ostream& operator<<(ostream&os, Op o) {
  os << "pos[ " << o.pos << " ] ";
  if (o.dir == Left) os << "Left";
  if (o.dir == Right) os << "Right";
  if (o.dir == Up) os << "Up";
  if (o.dir == Down) os << "Down";
  return os;
}

inline void
mov_left(vi&v, int n, int k) {
  char tmp = v[n*k];
  rep (i, n - 1) v[n*k+i] = v[n*k+i+1];
  v[n*k+n-1] = tmp;
}

inline void
mov_right(vi&v, int n, int k) {
  char tmp = v[n*k+n-1];
  rep (i, n - 1) v[n*k+n-i-1] = v[n*k+n-i-2];
  v[n*k] = tmp;
}

inline void
mov_up(vi&v, int n, int k) {
  char tmp = v[k];
  rep (i, n - 1) v[k + n * i] = v[k + n * (i+1)];
  v[k + (n-1)*n] = tmp;
}

inline void
mov_down(vi&v, int n, int k) {
  char tmp = v[k + (n-1)*n];
  rep (i, n - 1) v[k + n*(n-i-1)] = v[k + n*(n-i-2)];
  v[k] = tmp;
}

vector<pair<vi, Op>> step(int n, vi v) {
  vector<pair<vi, Op>> ret;
  rep (k, n) {
    mov_left(v, n, k);
    ret.push_back({ v, Op(k, Left) });
    mov_right(v, n, k);
    mov_right(v, n, k);
    ret.push_back({ v, Op(k, Right) });
    mov_left(v, n, k);
  }
  rep (k, n) {
    mov_up(v, n, k);
    ret.push_back({ v, Op(k, Up) });
    mov_down(v, n, k);
    mov_down(v, n, k);
    ret.push_back({ v, Op(k, Down) });
    mov_up(v, n, k);
  }
  return ret;
}

bool equal(vi&xs, vi&ys) {
  int n = xs.size();
  if (ys.size() != n) return false;
  rep (i, n)
    if (xs[i] != ys[i]) return false;
  return true;
}

map<vi, vector<Op>> memo;
map<vi, vector<Op>> r_memo;

int main(int argc, char*argv[]) {

  int n; cin >> n;
  vi f(n*n), g(n*n);
  rep (i, n*n) cin >> f[i];
  rep (i, n*n) cin >> g[i];
  trace(f); trace(g);

  vector<Op> ops;
  queue<pair<vi, bool>> q;
  q.push({ f, true });
  q.push({ g, false });

  memo[f] = {};
  r_memo[g] = {};

  while (not q.empty()) {
    auto tp = q.front(); q.pop();
    auto&f = tp.first;
    auto d = tp.second;

    if ((d and r_memo.count(f) > 0) or ((not d) and memo.count(f) > 0)) {
      for (auto&o: memo[f])
        cout << o << endl;
      for (int i = r_memo[f].size() - 1; i >= 0; --i) {
        Op&o = r_memo[f][i];
        o.dir = invert(o.dir);
        cout << r_memo[f][i] << endl;
      }
      return 0;
    }

    for (auto&p: step(n, f)) {
      auto&f2 = p.first;
      auto o = p.second;
      if (d) {
        if (memo.count(f2) > 0) continue;
        vector<Op> hs2 = memo[f];
        hs2.push_back(o);
        memo[f2] = hs2;
      } else {
        if (r_memo.count(f2) > 0) continue;
        vector<Op> hs2 = r_memo[f];
        hs2.push_back(o);
        r_memo[f2] = hs2;
      }
      q.push({f2, d});
    }
  }
  return 0;
}
$ cat input
4

YYYY
YGYG
RRGR
RGYY

YYYY
GGGG
RRRR
YYYY

$ ./a.out < input
pos[ 1 ] Up
pos[ 2 ] Up
pos[ 2 ] Left
pos[ 1 ] Down
pos[ 0 ] Up

pos[ m ] (\(0 \leq m < n\)) \(m\) ่กŒ็›ฎใ€ใพใŸใฏ \(m\) ๅˆ—็›ฎใ‚’่กจใ™
ใŸใ ใ—ใ€ ็›คใฎๆœ€ไธŠๆฎตใ‚’0่กŒ็›ฎใ€ๆœ€ๅทฆๅˆ—ใ‚’0ๅˆ—็›ฎใ ใจใ—ใฆๆ•ฐใˆใ‚‹
(ไบบ้–“ใŒ่ชญใ‚€้ƒจๅˆ†ใใ‚‰ใ„ใ€1-indexedใซใ™ใ‚‹ใ‚‚ใฎใ ใจๅ็œใ—ใŸ)

ไปŠใฎๅ ดๅˆ

  1. 1ๅˆ—็›ฎใ‚’ไธŠใซshift
  2. 2ๅˆ—็›ฎใ‚’ไธŠใซshift
  3. 2่กŒ็›ฎใ‚’ๅทฆใซshift
  4. 1ๅˆ—็›ฎใ‚’ไธ‹ใซshift
  5. 0ๅˆ—็›ฎใ‚’ไธŠใซshift

ใจใ„ใ†ๆ‰‹้ †ใ‚’่กจใ™

ๆ„Ÿๆƒณ

ไธ€ใคใฎใ‚นใƒ†ใƒผใ‚ธใ‚’ใ‚ฏใƒชใ‚ขใ™ใ‚‹ๅบฆใซใ€ ๅ…ฅๅŠ›ใ‚’ไฝœใ‚‹ไฝœๆฅญใŒไธ€็•ชใฎๆ‰‹้–“ใ ใฃใŸ