#include using namespace std; #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #pragma GCC target("avx2") // 数値型 using ll = long long; using ull = unsigned long long; using ld = long double; using P = pair; using Pll = pair; using Pli = pair; using Pil = pair; // vector関連 using vi = vector; using vvi = vector; using vvvi = vector; using vll = vector; using vvll = vector; using vvvll = vector; template using vc = vector; template using vvc = vector>; template using vvvc = vector>; template using vvvvc = vector>; // priority_queue template using pq = priority_queue; template using pqg = priority_queue, greater>; #define rep(i, n) for(int i = 0; i < (int)(n); i++) #define FOR(i, a, b) for(int i = a; i < (int)(b); i++) #define all(a) (a).begin(),(a).end() #define rall(a) (a).rbegin(),(a).rend() #define MIN(vec) *min_element(vec) #define MAX(vec) *max_element(vec) #define next_perm(vec) next_permutation((vec).begin(), (vec).end()) #define UNIQUE(vec) vec.erase(unique(vec.begin(), vec.end()), vec.end()) #define el "\n" #define Yes cout << "Yes" << el #define No cout << "No" << el #define YES cout << "YES" << el #define NO cout << "NO" << el #define EPS 1e-8 #define Equal(a, b) (fabs((a)-(b)) < EPS) #define dbg(x) cerr << #x << "=" << x << el // 定数 const string abc = "abcdefghijklmnopqrstuvwxyz"; const string ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; constexpr int INF = 1001001001; constexpr ll LINF = 1001001001001001001ll; constexpr int DX[] = {1, 0, -1, 0}; constexpr int DY[] = {0, 1, 0, -1}; constexpr int DX8[] = {1, 0, -1, 0, 1, 1, -1, -1}; constexpr int DY8[] = {0, 1, 0, -1, 1, -1, 1, -1}; template ostream &operator<< (ostream &os, pair p) { os << "{" << p.first << "," << p.second << "}"; return os; } template ostream &operator<< (ostream &os, vc &vec) { int sz = vec.size(); rep(i, sz){ os << vec[i] << (i==sz-1?"":" "); } return os; } template istream &operator>> (istream &is, pair &p) { is >> p.first >> p.second; return is; } template istream &operator>> (istream &is, vc &vec) { int sz = vec.size(); rep(i, sz) { is >> vec[i]; } return is; } /// @brief aとbの最大値をaに格納。更新があったかbool値を返す /// @tparam T1 /// @tparam T2 /// @param a /// @param b /// @return bool template inline bool chmax(T1 &a, T2 b){ bool ret = a inline bool chmin(T1 &a, T2 b){ bool ret = a>b; if(ret) {a = b;} return ret; } inline void YesNo(bool flag){ if(flag) {Yes;} else {No;} return; } inline void YESNO(bool flag){ if(flag) {YES;} else {NO;} return; } inline bool outof(ll x, ll xlim){ return (x<0 || x>=xlim); } template inline T sqnorm(T x, T y){ return x*x+y*y; } /// @brief char->int /// @param c /// @return int inline int ctoi(char c){ return c-'0'; } /// @brief xを素因数分解 /// @param x /// @return vector, 素因数の昇順に {p, cnt} vector prime_fact(ll x){ vector ret; for(ll i=2; i*i<=x; i++){ if(x%i == 0){ ret.emplace_back(i, 0); while(x%i == 0){ ret.back().second++; x /= i; } } } if(x != 1) ret.emplace_back(x, 1); return ret; } /// @brief xの約数列挙 /// @param x /// @return vll, 約数の昇順 vll divisor_enum(ll x){ vector ret; for(ll i=1; i*i<=x; i++){ if(x%i == 0){ ret.push_back(x/i); ret.push_back(i); } } sort(all(ret)); UNIQUE(ret); return ret; } /// @brief 繰り返し二乗法。 /// @tparam T /// @param x /// @param k /// @param op /// @param e /// @return template T pow_t(T x, ll k, T (*op)(T, T), T (*e)()){ T ret = e(); while(k){ if(k&1) ret = op(ret, x); x = op(x, x); k >>= 1; } return ret; } ll powll(ll x, ll k){ return pow_t(x, k, [](ll a, ll b) -> ll{return a*b;}, []() -> ll{return 1;}); } inline int pop_cnt(ll x) { return __builtin_popcountll(x); } inline int top_bit(ll x) { return (x==0?-1:63-__builtin_clzll(x));} void main2(); int main(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); main2(); } void main2(){ int n, k; cin >> n >> k; P s, t; cin >> s >> t; s.first--; s.second--; t.first--; t.second--; if(s.first > t.first) swap(s, t); int d = abs(s.first - t.first) + abs(s.second - t.second); if((s.first+s.second+t.first+t.second)%2 != k%2 || d*2 < k || d > k) { cout << -1 << el; return; } vc ans(n, string(n, '.')); rep(i, n) { rep(j, n) { if((i+j)%2 != (s.first+s.second)%2) { ans[i][j] = '#'; } } } ans[t.first][t.second] = '.'; deque> que; vvi dp(n, vi(n, INF)); vvc

pre(n, vc

(n, {-1, -1})); dp[s.first][s.second] = 0; que.push_back({{s.first, s.second}, 0}); while(!que.empty()) { auto [p, dd] = que.front(); que.pop_front(); if(dd != dp[p.first][p.second]) continue; rep(dir, 4) { P np = {p.first + DX[dir], p.second + DY[dir]}; if(outof(np.first, n) || outof(np.second, n)) continue; int nd = dd + (ans[np.first][np.second] != ans[p.first][p.second]) + 1; if(dp[np.first][np.second] <= nd) continue; pre[np.first][np.second] = p; dp[np.first][np.second] = nd; if(nd-dd == 2) que.push_back({np, nd}); else que.push_front({np, nd}); } } int now = dp[t.first][t.second]; P pos = {t.first, t.second}; while(now > k && pos != s) { if(ans[pos.first][pos.second] == '#') { now -= 2; ans[pos.first][pos.second] = '.'; } pos = pre[pos.first][pos.second]; } assert(now == k); rep(i, n) cout << ans[i] << el; }