Submission #69571774

---

Source Code Expand

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

int N, t_i, t_j;
vector<vector<char>> grid;
set<pair<int, int>> revealed;
set<pair<int, int>> placed_treants;
int entrance_i, entrance_j;
int turn_count = 0;

int di[4] = {-1, 1, 0, 0};
int dj[4] = {0, 0, -1, 1};

// 预计算距离矩阵
vector<vector<int>> dist_from_entrance;
vector<vector<int>> dist_from_flower;

// 快速BFS计算距离
void bfs_distance(int si, int sj, vector<vector<int>>& dist, const vector<vector<char>>& map) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            dist[i][j] = INT_MAX;
        }
    }
    
    queue<pair<int, int>> q;
    q.push(make_pair(si, sj));
    dist[si][sj] = 0;
    
    while (!q.empty()) {
        int i = q.front().first;
        int j = q.front().second;
        q.pop();
        
        for (int d = 0; d < 4; d++) {
            int ni = i + di[d], nj = j + dj[d];
            if (ni >= 0 && ni < N && nj >= 0 && nj < N && 
                dist[ni][nj] == INT_MAX && map[ni][nj] == '.') {
                dist[ni][nj] = dist[i][j] + 1;
                q.push(make_pair(ni, nj));
            }
        }
    }
}

// 快速连通性检查 - 只检查是否可达，不计算路径
bool is_connected_fast(int si, int sj, int ei, int ej, const vector<vector<char>>& map) {
    if (map[si][sj] == 'T' || map[ei][ej] == 'T') return false;
    
    vector<vector<bool>> visited(N, vector<bool>(N, false));
    queue<pair<int, int>> q;
    q.push(make_pair(si, sj));
    visited[si][sj] = true;
    
    while (!q.empty()) {
        int i = q.front().first;
        int j = q.front().second;
        q.pop();
        
        if (i == ei && j == ej) return true;
        
        for (int d = 0; d < 4; d++) {
            int ni = i + di[d], nj = j + dj[d];
            if (ni >= 0 && ni < N && nj >= 0 && nj < N && 
                !visited[ni][nj] && map[ni][nj] == '.') {
                visited[ni][nj] = true;
                q.push(make_pair(ni, nj));
            }
        }
    }
    return false;
}

// 获取最短路径（简化版，只找一条路径）
vector<pair<int, int>> get_shortest_path_fast(int si, int sj, int ei, int ej, const vector<vector<char>>& map) {
    if (map[si][sj] == 'T' || map[ei][ej] == 'T') return {};
    
    vector<vector<pair<int, int>>> prev(N, vector<pair<int, int>>(N, make_pair(-1, -1)));
    vector<vector<bool>> visited(N, vector<bool>(N, false));
    queue<pair<int, int>> q;
    q.push(make_pair(si, sj));
    visited[si][sj] = true;
    
    while (!q.empty()) {
        int i = q.front().first;
        int j = q.front().second;
        q.pop();
        
        if (i == ei && j == ej) {
            vector<pair<int, int>> path;
            int cur_i = i, cur_j = j;
            while (cur_i != si || cur_j != sj) {
                path.push_back(make_pair(cur_i, cur_j));
                pair<int, int> p = prev[cur_i][cur_j];
                cur_i = p.first;
                cur_j = p.second;
            }
            path.push_back(make_pair(si, sj));
            reverse(path.begin(), path.end());
            return path;
        }
        
        // 优先选择更接近目标的方向
        vector<int> dir_priority = {0, 1, 2, 3};
        if (ei > i) swap(dir_priority[0], dir_priority[1]); // 优先向下
        if (ej > j) swap(dir_priority[2], dir_priority[3]); // 优先向右
        
        for (int d_idx = 0; d_idx < 4; d_idx++) {
            int d = dir_priority[d_idx];
            int ni = i + di[d], nj = j + dj[d];
            if (ni >= 0 && ni < N && nj >= 0 && nj < N && 
                !visited[ni][nj] && map[ni][nj] == '.') {
                visited[ni][nj] = true;
                prev[ni][nj] = make_pair(i, j);
                q.push(make_pair(ni, nj));
            }
        }
    }
    return {};
}

// 快速评估位置价值
int evaluate_position_fast(int i, int j, int p_i, int p_j, bool flower_revealed) {
    int score = 0;
    
    // 1. 距离花朵的远近
    int flower_dist = abs(i - t_i) + abs(j - t_j);
    score += max(0, 15 - flower_dist);
    
    // 2. 如果花朵已揭示，优先阻塞路径
    if (flower_revealed) {
        // 简单评估：如果这个位置在冒险者和花朵之间
        if ((i >= min(p_i, t_i) && i <= max(p_i, t_i)) && 
            (j >= min(p_j, t_j) && j <= max(p_j, t_j))) {
            score += 20;
        }
    } else {
        // 3. 如果花朵未揭示，在花朵周围形成保护
        if (flower_dist <= 3) {
            score += 25;
        }
        
        // 4. 在冒险者和花朵之间的位置
        int mid_i = (p_i + t_i) / 2;
        int mid_j = (p_j + t_j) / 2;
        if (abs(i - mid_i) + abs(j - mid_j) <= 2) {
            score += 15;
        }
    }
    
    // 5. 创建死胡同的潜力
    int revealed_neighbors = 0;
    for (int d = 0; d < 4; d++) {
        int ni = i + di[d], nj = j + dj[d];
        if (ni >= 0 && ni < N && nj >= 0 && nj < N) {
            if (revealed.find(make_pair(ni, nj)) != revealed.end()) {
                revealed_neighbors++;
            }
        }
    }
    
    // 如果周围有已揭示的单元格，这个位置更有价值
    score += revealed_neighbors * 3;
    
    return score;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // 读取输入
    cin >> N >> t_i >> t_j;
    grid.resize(N, vector<char>(N));
    for (int i = 0; i < N; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < N; j++) {
            grid[i][j] = s[j];
        }
    }
    
    entrance_i = 0;
    entrance_j = N / 2;
    revealed.insert(make_pair(entrance_i, entrance_j));
    
    // 初始化距离矩阵
    dist_from_entrance.resize(N, vector<int>(N, INT_MAX));
    dist_from_flower.resize(N, vector<int>(N, INT_MAX));
    
    // 预计算距离
    bfs_distance(entrance_i, entrance_j, dist_from_entrance, grid);
    bfs_distance(t_i, t_j, dist_from_flower, grid);
    
    // 主循环
    while (true) {
        turn_count++;
        int p_i, p_j;
        cin >> p_i >> p_j;
        
        int n;
        cin >> n;
        vector<pair<int, int>> new_revealed;
        for (int i = 0; i < n; i++) {
            int x, y;
            cin >> x >> y;
            revealed.insert(make_pair(x, y));
            new_revealed.push_back(make_pair(x, y));
        }
        
        // 检查是否到达花朵
        if (p_i == t_i && p_j == t_j) {
            break;
        }
        
        // 构建真实地图
        vector<vector<char>> real_map = grid;
        for (auto& pos : placed_treants) {
            real_map[pos.first][pos.second] = 'T';
        }
        
        // 构建试探地图
        vector<vector<char>> tentative_map(N, vector<char>(N, '.'));
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (revealed.find(make_pair(i, j)) != revealed.end()) {
                    tentative_map[i][j] = real_map[i][j];
                }
            }
        }
        
        // 获取可放置位置（限制数量）
        vector<pair<int, int>> available_positions;
        int max_positions = 100; // 限制评估的位置数量
        
        // 优先考虑关键区域的位置
        bool flower_revealed = revealed.find(make_pair(t_i, t_j)) != revealed.end();
        
        // 区域1: 花朵周围
        for (int i = max(0, t_i-3); i <= min(N-1, t_i+3) && available_positions.size() < max_positions; i++) {
            for (int j = max(0, t_j-3); j <= min(N-1, t_j+3); j++) {
                if (revealed.find(make_pair(i, j)) == revealed.end() && 
                    real_map[i][j] == '.') {
                    available_positions.push_back(make_pair(i, j));
                    if (available_positions.size() >= max_positions) break;
                }
            }
        }
        
        // 区域2: 冒险者和花朵之间
        if (available_positions.size() < max_positions) {
            int mid_i = (p_i + t_i) / 2;
            int mid_j = (p_j + t_j) / 2;
            for (int i = max(0, mid_i-2); i <= min(N-1, mid_i+2) && available_positions.size() < max_positions; i++) {
                for (int j = max(0, mid_j-2); j <= min(N-1, mid_j+2); j++) {
                    if (revealed.find(make_pair(i, j)) == revealed.end() && 
                        real_map[i][j] == '.' &&
                        find(available_positions.begin(), available_positions.end(), make_pair(i, j)) == available_positions.end()) {
                        available_positions.push_back(make_pair(i, j));
                        if (available_positions.size() >= max_positions) break;
                    }
                }
            }
        }
        
        // 区域3: 随机补充
        if (available_positions.size() < max_positions / 2) {
            // 如果关键区域位置太少，随机补充一些
            for (int i = 0; i < N && available_positions.size() < max_positions; i++) {
                for (int j = 0; j < N && available_positions.size() < max_positions; j++) {
                    if (revealed.find(make_pair(i, j)) == revealed.end() && 
                        real_map[i][j] == '.' &&
                        find(available_positions.begin(), available_positions.end(), make_pair(i, j)) == available_positions.end()) {
                        available_positions.push_back(make_pair(i, j));
                    }
                }
            }
        }
        
        if (available_positions.empty()) {
            cout << 0 << endl;
            continue;
        }
        
        // 快速选择最佳位置
        pair<int, int> best_pos = make_pair(-1, -1);
        int best_score = -1;
        
        // 限制评估的数量
        int max_evaluate = min(30, (int)available_positions.size());
        
        // 第一阶段：快速筛选
        vector<pair<int, pair<int, int>>> candidates;
        for (int idx = 0; idx < max_evaluate; idx++) {
            int i = available_positions[idx].first;
            int j = available_positions[idx].second;
            
            // 快速连通性检查
            vector<vector<char>> test_map = real_map;
            test_map[i][j] = 'T';
            if (!is_connected_fast(entrance_i, entrance_j, t_i, t_j, test_map)) {
                continue;
            }
            
            int score = evaluate_position_fast(i, j, p_i, p_j, flower_revealed);
            
            // 如果是花朵已揭示阶段，检查是否在路径上
            if (flower_revealed) {
                auto path = get_shortest_path_fast(p_i, p_j, t_i, t_j, tentative_map);
                for (const auto& pos : path) {
                    if (pos.first == i && pos.second == j) {
                        score += 30;
                        break;
                    }
                }
            }
            
            candidates.push_back(make_pair(score, make_pair(i, j)));
        }
        
        // 第二阶段：精细评估（只对前几名候选）
        if (!candidates.empty()) {
            sort(candidates.begin(), candidates.end(), greater<pair<int, pair<int, int>>>());
            
            // 只评估前3名候选的路径影响
            int top_n = min(3, (int)candidates.size());
            for (int i = 0; i < top_n; i++) {
                int score = candidates[i].first;
                int pos_i = candidates[i].second.first;
                int pos_j = candidates[i].second.second;
                
                // 计算路径长度影响
                if (flower_revealed) {
                    int original_length = get_shortest_path_fast(p_i, p_j, t_i, t_j, tentative_map).size();
                    if (original_length > 0) {
                        vector<vector<char>> test_tentative = tentative_map;
                        test_tentative[pos_i][pos_j] = 'T';
                        int new_length = get_shortest_path_fast(p_i, p_j, t_i, t_j, test_tentative).size();
                        if (new_length > 0) {
                            score += (new_length - original_length) * 2;
                        }
                    }
                }
                
                if (score > best_score) {
                    best_score = score;
                    best_pos = candidates[i].second;
                }
            }
        }
        
        // 输出结果
        if (best_pos.first != -1) {
            placed_treants.insert(best_pos);
            cout << 1 << " " << best_pos.first << " " << best_pos.second << endl;
        } else {
            // 尝试找到一个安全位置
            bool found = false;
            for (const auto& pos : available_positions) {
                vector<vector<char>> test_map = real_map;
                test_map[pos.first][pos.second] = 'T';
                if (is_connected_fast(entrance_i, entrance_j, t_i, t_j, test_map)) {
                    placed_treants.insert(pos);
                    cout << 1 << " " << pos.first << " " << pos.second << endl;
                    found = true;
                    break;
                }
            }
            if (!found) {
                cout << 0 << endl;
            }
        }
        
        // 防止超时
        if (turn_count > 2000) {
            cout << -1 << endl;
            break;
        }
    }
    
    return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:240:88: warning: comparison of integer expressions of different signedness: ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
  240 |         for (int i = max(0, t_i-3); i <= min(N-1, t_i+3) && available_positions.size() < max_positions; i++) {
      |                                                             ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
Main.cpp:245:52: warning: comparison of integer expressions of different signedness: ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
  245 |                     if (available_positions.size() >= max_positions) break;
      |                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
Main.cpp:251:40: warning: comparison of integer expressions of different signedness: ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
  251 |         if (available_positions.size() < max_positions) {
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
Main.cpp:254:96: warning: comparison of integer expressions of different signedness: ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
  254 |             for (int i = max(0, mid_i-2); i <= min(N-1, mid_i+2) && available_positions.size() < max_positions; i++) {
      |                                                                     ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
Main.cpp:260:56: warning: comparison of integer expressions of different signedness: ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
  260 |                         if (available_positions.size() >= max_positions) break;
      |                             ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
Main.cpp:267:40: warning: comparison of integer expressions of different signedness: ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
  267 |         if (available_positions.size() < max_positions / 2) {
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:269:65: warning: comparison of integer expressions of different signedness: ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
  269 |             for (int i = 0; i < N && available_positions.size() < max_positions; i++) {
      |                                      ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
Main.cpp:270:69: warning: comparison of integer expressions of different signedness: ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
  270 |                 for (int j = 0; j < N && available_positions.size() < max_positions; j++) {
      |                                          ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~

Judge Result