#include #include #include #include #include #include #include #include // ビームサーチの重複状態管理に使えるかも #include using namespace std; // 定数 const int N = 10; const int MAX_T = 1000; const int MAX_BIT = 20; // グリッドの状態 vector> initial_A_bs; // 初期グリッドを保持 // 盤面状態を保持する構造体 (ビームサーチ用) struct BS_BoardState { vector> current_A; int current_r, current_c; int s_val; vector operations; long long score; // 評価関数値 // コンストラクタ BS_BoardState() : current_r(0), current_c(0), s_val(0), score(0) {} // 初期化 void init(const vector>& initial_grid) { current_A = initial_grid; current_r = 0; current_c = 0; s_val = 0; operations.clear(); score = calculate_score(); // 初期スコア計算 } // 操作を適用して新しい状態を返す BS_BoardState apply_op_and_get_new_state(const string& op) const { BS_BoardState new_state = *this; // 現在の状態をコピー // 無効な操作のチェック if (op == "U" && new_state.current_r == 0) return new_state; // 変更しない if (op == "D" && new_state.current_r == N - 1) return new_state; if (op == "L" && new_state.current_c == 0) return new_state; if (op == "R" && new_state.current_c == N - 1) return new_state; new_state.operations.push_back(op); if (op == "U") new_state.current_r--; else if (op == "D") new_state.current_r++; else if (op == "L") new_state.current_c--; else if (op == "R") new_state.current_c++; else if (op == "W") new_state.current_A[new_state.current_r][new_state.current_c] ^= new_state.s_val; else if (op == "C") new_state.s_val ^= new_state.current_A[new_state.current_r][new_state.current_c]; new_state.score = new_state.calculate_score(); // スコアを再計算 return new_state; } // スコア計算 (constメソッドにする) long long calculate_score() const { long long current_score = 0; for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { current_score += current_A[i][j]; } } return current_score; } }; // スコアでソートするための比較関数 (ビームサーチ用) bool compareBS_BoardStates(const BS_BoardState& a, const BS_BoardState& b) { return a.score > b.score; // スコアが高い方を優先 } // ビームサーチのメイン関数 vector beam_search(const vector>& initial_grid, int beam_width = 100) { vector current_beam; BS_BoardState initial_state; initial_state.init(initial_grid); current_beam.push_back(initial_state); vector best_operations = initial_state.operations; long long max_overall_score = initial_state.score; string possible_ops[] = {"U", "D", "L", "R", "W", "C"}; for (int t = 0; t < MAX_T; ++t) { vector next_beam; if (current_beam.empty()) break; // 探索するパスがなくなったら終了 for (const auto& state : current_beam) { for (const string& op_str : possible_ops) { BS_BoardState new_state = state.apply_op_and_get_new_state(op_str); next_beam.push_back(new_state); } } // 次のビームをソートし、ビーム幅で刈り取る sort(next_beam.begin(), next_beam.end(), compareBS_BoardStates); // 重複状態の除去 (任意だが、効率改善のため) // map>, int, int, int>, bool> visited; // vector unique_next_beam; // for(const auto& state : next_beam) { // // 状態を一意に識別するキーを作成 (A, r, c, s_val) // // 注意: Aをキーに含めるとvector>はtupleに直接入れられないので、ハッシュ化など工夫が必要 // // あるいは、visitedを使わず、単にスコアで選ぶだけにする。 // unique_next_beam.push_back(state); // 今回は簡略化のためそのまま追加 // } // next_beam = unique_next_beam; if (next_beam.size() > beam_width) { next_beam.resize(beam_width); } current_beam = next_beam; // 全体でのベストスコアを更新 if (!current_beam.empty() && current_beam[0].score > max_overall_score) { max_overall_score = current_beam[0].score; best_operations = current_beam[0].operations; } } // 最終的なビームの中で最も良いものを選択 if (!current_beam.empty()) { sort(current_beam.begin(), current_beam.end(), compareBS_BoardStates); if (current_beam[0].score > max_overall_score) { best_operations = current_beam[0].operations; } } return best_operations; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int dummy_N, dummy_T; cin >> dummy_N >> dummy_T; initial_A_bs.resize(N, vector(N)); for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { cin >> initial_A_bs[i][j]; } } // どちらか一方を選択して呼び出す // vector final_operations = simulated_annealing(initial_A_bs, 1900); // 1.9秒で実行 vector final_operations = beam_search(initial_A_bs, 50); // ビーム幅 200 (要調整) for (const string& op : final_operations) { cout << op << endl; } return 0; }