結果
| 問題 |
No.640 76本のトロンボーン
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:09:30 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 10,077 bytes |
| コンパイル時間 | 1,349 ms |
| コンパイル使用メモリ | 97,248 KB |
| 実行使用メモリ | 11,300 KB |
| 最終ジャッジ日時 | 2025-05-14 13:10:48 |
| 合計ジャッジ時間 | 4,875 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 2 |
| other | AC * 7 TLE * 1 -- * 7 |
ソースコード
#include <iostream>
#include <vector>
#include <string>
#include <vector>
#include <numeric>
#include <algorithm>
#include <map>
using namespace std;
// Grid size
int N;
// Grid representation
vector<string> grid;
// Structure to represent a trombone placement
struct Trombone {
int id; // Unique identifier for the trombone placement
int type; // 0 for horizontal, 1 for vertical
int rc_idx; // row index for horizontal, column index for vertical (0-based)
int start_pos; // Indicates start position:
// For horizontal: 1 means covering columns 0 to N-2, 2 means columns 1 to N-1
// For vertical: 1 means covering rows 0 to N-2, 2 means rows 1 to N-1
};
// List of all valid trombone placements found
vector<Trombone> trombones;
// Adjacency list representation of the conflict graph
// Maps a trombone ID to a list of IDs of trombones it conflicts with
map<int, vector<int>> adj;
// Stores the maximum size of the independent set found so far
int max_is_size = 0;
// List of all trombone IDs (assumed to be 0 to total_trombones-1)
vector<int> nodes_list;
// Tracks which trombones are currently selected in the recursive search
vector<bool> current_selection;
/**
* @brief Recursive backtracking function to find the Maximum Independent Set (MIS).
*
* Finds the maximum number of trombones that can be placed without conflicts.
* It explores possibilities by trying to include or exclude each trombone placement.
*
* @param k_idx Index of the current trombone in nodes_list being considered.
* @param current_max The size of the independent set built so far in the current recursive path.
*/
void find_max_is_recursive(int k_idx, int current_max) {
int num_nodes = nodes_list.size();
// Base case: If all trombones have been considered
if (k_idx == num_nodes) {
// Update the global maximum MIS size found
max_is_size = max(max_is_size, current_max);
return;
}
// Get the ID of the current trombone being considered
int node_id = nodes_list[k_idx];
// Pruning optimization: If the current path plus all remaining nodes cannot possibly
// exceed the best MIS size found so far, then prune this branch.
if (current_max + (num_nodes - k_idx) <= max_is_size) {
return;
}
// Branch 1: Try including the current trombone (node_id) in the independent set
bool can_include = true;
// Check if node_id exists in the adjacency list map
if (adj.count(node_id)) {
// Check if including node_id conflicts with any previously selected trombone
// A conflict occurs if any neighbor of node_id is already selected.
// Since we process nodes in order (0 to num_nodes-1), we only need to check neighbors
// that have already been processed (their decision made).
// The `current_selection` array tracks this.
for (int neighbor_id : adj.at(node_id)) {
// Ensure neighbor_id is within bounds and check if it's selected
if (neighbor_id < current_selection.size() && current_selection[neighbor_id]) {
can_include = false;
break;
}
}
}
// If it's safe to include node_id
if (can_include) {
// Mark node_id as selected
current_selection[node_id] = true;
// Recurse for the next trombone, incrementing the current IS size
find_max_is_recursive(k_idx + 1, current_max + 1);
// Backtrack: Unmark node_id to explore other possibilities
current_selection[node_id] = false;
}
// Branch 2: Try excluding the current trombone (node_id) from the independent set
// Recurse for the next trombone without changing the current IS size
find_max_is_recursive(k_idx + 1, current_max);
}
int main() {
// Faster I/O
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// Read grid size N
cin >> N;
// Read grid state
grid.resize(N);
for (int i = 0; i < N; ++i) {
cin >> grid[i];
}
// Assign unique IDs starting from 0
int current_id = 0;
// Identify all valid horizontal trombone placements
for (int r = 0; r < N; ++r) {
// Check placement type 1: Row r, columns 0 to N-2
bool possible1 = true;
if (N > 1) { // A trombone requires at least length 1 (N>=2)
for (int c = 0; c < N - 1; ++c) {
if (grid[r][c] == '#') { // Check for obstacles
possible1 = false;
break;
}
}
// If no obstacles found, add this placement as a valid trombone
if (possible1) {
trombones.push_back({current_id++, 0, r, 1});
}
}
// Check placement type 2: Row r, columns 1 to N-1
bool possible2 = true;
if (N > 1) {
for (int c = 1; c < N; ++c) {
if (grid[r][c] == '#') { // Check for obstacles
possible2 = false;
break;
}
}
// If no obstacles found, add this placement
if (possible2) {
trombones.push_back({current_id++, 0, r, 2});
}
}
}
// Identify all valid vertical trombone placements
for (int c = 0; c < N; ++c) {
// Check placement type 1: Column c, rows 0 to N-2
bool possible1 = true;
if (N > 1) {
for (int r = 0; r < N - 1; ++r) {
if (grid[r][c] == '#') { // Check for obstacles
possible1 = false;
break;
}
}
// If valid, add placement
if (possible1) {
trombones.push_back({current_id++, 1, c, 1});
}
}
// Check placement type 2: Column c, rows 1 to N-1
bool possible2 = true;
if (N > 1) {
for (int r = 1; r < N; ++r) {
if (grid[r][c] == '#') { // Check for obstacles
possible2 = false;
break;
}
}
// If valid, add placement
if (possible2) {
trombones.push_back({current_id++, 1, c, 2});
}
}
}
// Total number of valid trombone placements identified
int total_trombones = trombones.size();
// If no trombones can be placed, the answer is 0
if (total_trombones == 0) {
cout << 0 << endl;
return 0;
}
// Build the conflict graph represented by the adjacency list `adj`
for (int i = 0; i < total_trombones; ++i) {
for (int j = i + 1; j < total_trombones; ++j) {
Trombone t1 = trombones[i];
Trombone t2 = trombones[j];
bool conflict = false; // Flag to indicate if t1 and t2 conflict
// Case 1: Both are horizontal trombones
if (t1.type == 0 && t2.type == 0) {
// Conflict if they are in the same row
if (t1.rc_idx == t2.rc_idx) {
conflict = true;
}
// Case 2: Both are vertical trombones
} else if (t1.type == 1 && t2.type == 1) {
// Conflict if they are in the same column
if (t1.rc_idx == t2.rc_idx) {
conflict = true;
}
// Case 3: One horizontal, one vertical trombone
} else {
// Determine which is horizontal (h_trom) and which is vertical (v_trom)
Trombone h_trom = (t1.type == 0) ? t1 : t2;
Trombone v_trom = (t1.type == 1) ? t1 : t2;
// Get coordinates and start types
int r = h_trom.rc_idx; // row index (0-based) of horizontal trombone
int h_start_col = h_trom.start_pos; // start type (1 or 2) of horizontal trombone
int c = v_trom.rc_idx; // column index (0-based) of vertical trombone
int v_start_row = v_trom.start_pos; // start type (1 or 2) of vertical trombone
// Convert row/col indices to 1-based for easier logic matching with problem statement
int r_1based = r + 1;
int c_1based = c + 1;
// Check if the horizontal trombone covers cell (r, c)
bool h_covers = false;
if (h_start_col == 1 && c_1based >= 1 && c_1based <= N - 1) h_covers = true; // Type 1 covers cols 1 to N-1
if (h_start_col == 2 && c_1based >= 2 && c_1based <= N) h_covers = true; // Type 2 covers cols 2 to N
// Check if the vertical trombone covers cell (r, c)
bool v_covers = false;
if (v_start_row == 1 && r_1based >= 1 && r_1based <= N - 1) v_covers = true; // Type 1 covers rows 1 to N-1
if (v_start_row == 2 && r_1based >= 2 && r_1based <= N) v_covers = true; // Type 2 covers rows 2 to N
// Conflict occurs if both cover the intersection cell (r, c)
if (h_covers && v_covers) {
conflict = true;
}
}
// If a conflict exists, add edges between their IDs in the adjacency list
if (conflict) {
adj[t1.id].push_back(t2.id);
adj[t2.id].push_back(t1.id);
}
}
}
// Prepare for the recursive search
// Fill nodes_list with trombone IDs (0 to current_id-1)
for(int i=0; i<current_id; ++i) nodes_list.push_back(i);
// Resize the selection tracking vector to hold status for all IDs
current_selection.resize(current_id, false);
// Start the recursive backtracking search for the Maximum Independent Set
find_max_is_recursive(0, 0);
// Output the maximum size found
cout << max_is_size << endl;
return 0;
}