回転 (rotation)
(include/emthrm/misc/rotate.hpp)

• View this file on GitHub
• Last update: 2023-02-23 21:59:12+09:00
• Include: #include "emthrm/misc/rotate.hpp"

点の回転は

• $45^\circ$ のとき $(x, y) \rightarrow (x - y, x + y)$、
• $90^\circ$ のとき $(x, y) \rightarrow (-y, x)$

と変換すればよい。

時間計算量

$O(HW)$

仕様

名前	戻り値	要件
template <int ANGLE, typename T> std::vector<std::vector<T>> rotate(const std::vector<std::vector<T>>& grid, const T space = ' ');	グリッド $\mathrm{grid}$ を $\mathrm{ANGLE}$ 度だけ回転させたもの	$\mathrm{ANGLE} \in \lbrace 45, 90 \rbrace$

参考文献

• https://kagamiz.hatenablog.com/entry/2014/12/21/213931

Submissons

https://onlinejudge.u-aizu.ac.jp/solutions/problem/2953/review/4082725/emthrm/C++14

Verified with

• その他/回転 (test/misc/rotate.test.cpp)

Code

#ifndef EMTHRM_MISC_ROTATE_HPP_
#define EMTHRM_MISC_ROTATE_HPP_

#include <cassert>
#include <vector>

namespace emthrm {

template <int ANGLE, typename T>
std::vector<std::vector<T>> rotate(const std::vector<std::vector<T>>& grid,
                                   const T space = ' ') {
  static_assert(ANGLE == 45 || ANGLE == 90);
  const int h = grid.size(), w = grid.front().size();
  std::vector<std::vector<T>> rotated_grid;
  if constexpr (ANGLE == 45) {
    rotated_grid.assign(h + w - 1, std::vector<T>(h + w - 1, space));
    for (int i = 0; i < h; ++i) {
      for (int j = 0; j < w; ++j) {
        rotated_grid[i + j][i - j + w - 1] = grid[i][j];
      }
    }
  } else {
    rotated_grid.assign(w, std::vector<T>(h));
    for (int i = 0; i < h; ++i) {
      for (int j = 0; j < w; ++j) {
        rotated_grid[w - 1 - j][i] = grid[i][j];
      }
    }
  }
  return rotated_grid;
}

}  // namespace emthrm

#endif  // EMTHRM_MISC_ROTATE_HPP_

#line 1 "include/emthrm/misc/rotate.hpp"



#include <cassert>
#include <vector>

namespace emthrm {

template <int ANGLE, typename T>
std::vector<std::vector<T>> rotate(const std::vector<std::vector<T>>& grid,
                                   const T space = ' ') {
  static_assert(ANGLE == 45 || ANGLE == 90);
  const int h = grid.size(), w = grid.front().size();
  std::vector<std::vector<T>> rotated_grid;
  if constexpr (ANGLE == 45) {
    rotated_grid.assign(h + w - 1, std::vector<T>(h + w - 1, space));
    for (int i = 0; i < h; ++i) {
      for (int j = 0; j < w; ++j) {
        rotated_grid[i + j][i - j + w - 1] = grid[i][j];
      }
    }
  } else {
    rotated_grid.assign(w, std::vector<T>(h));
    for (int i = 0; i < h; ++i) {
      for (int j = 0; j < w; ++j) {
        rotated_grid[w - 1 - j][i] = grid[i][j];
      }
    }
  }
  return rotated_grid;
}

}  // namespace emthrm

Back to top page