問題概要

n×nのサイズの迷路があり、各セルには0または1が書かれています。現在位置が0の場合、上下左右の隣接する4つのセルのうち1のセルに移動できます。同様に、現在位置が1の場合は、隣接する0のセルに移動可能です。この迷路に対して、指定された開始位置から移動可能なセルの総数（開始位置を含む）を求める問題です。

入力形式

1行目：正整数 n, m（迷路のサイズとクエリ数）
続くn行：各行にn個の文字（0または1）からなる迷路データ
続くm行：各行に2つの正整数 i, j（クエリ対象の行番号と列番号）

出力形式

m行の解答：各クエリに対して、指定位置から到達可能なセルの総数を出力

制約

• 20%のテストケース：n ≤ 10
• 40%のテストケース：n ≤ 50
• 50%のテストケース：m ≤ 5
• 60%のテストケース：n ≤ 100, m ≤ 100
• 100%のテストケース：n ≤ 1000, m ≤ 100000

解法アプローチ

この問題は深さ優先探索（DFS）または幅優先探索（BFS）のいずれかで解決できます。重要な最適化として、連結成分ごとに到達可能セル数を事前計算し、メモ化することで、複数のクエリを効率的に処理できます。

DFSによる実装

#include <iostream>
#include <vector>
#include <string>
#define GRID_SIZE 1010

using namespace std;

int dimension, queries, component_id;
int visited[GRID_SIZE][GRID_SIZE], component[GRID_SIZE][GRID_SIZE];
int reachable_count[GRID_SIZE * GRID_SIZE];
string maze[GRID_SIZE];

// 方位ベクトル：上、下、右、左
int directions[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

void explore_path(int row, int col) {
    visited[row][col] = 1;
    component[row][col] = component_id;
    reachable_count[component_id]++;
    
    for (int dir = 0; dir < 4; dir++) {
        int next_row = row + directions[dir][0];
        int next_col = col + directions[dir][1];
        
        if (next_row < 0 || next_row >= dimension || 
            next_col < 0 || next_col >= dimension ||
            visited[next_row][next_col] ||
            maze[next_row][next_col] == maze[row][col]) {
            continue;
        }
        
        explore_path(next_row, next_col);
    }
}

void solve_dfs() {
    cin >> dimension >> queries;
    
    for (int i = 0; i < dimension; i++) {
        cin >> maze[i];
    }
    
    component_id = 0;
    for (int i = 0; i < dimension; i++) {
        for (int j = 0; j < dimension; j++) {
            if (!component[i][j]) {
                component_id++;
                explore_path(i, j);
            }
        }
    }
    
    while (queries--) {
        int query_row, query_col;
        cin >> query_row >> query_col;
        cout << reachable_count[component[query_row - 1][query_col - 1]] << endl;
    }
}

int main() {
    solve_dfs();
    return 0;
}

BFSによる実装

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#define MAX_DIM 1010

using namespace std;

struct Position {
    int x, y;
};

int width, height, group_counter;
int grid[MAX_DIM][MAX_DIM], group_id[MAX_DIM][MAX_DIM];
int group_size[MAX_DIM * MAX_DIM];
bool processed[MAX_DIM][MAX_DIM];
string layout[MAX_DIM];

// 移動方向：北、南、東、西
int movement[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

void breadth_first_search(int start_x, int start_y) {
    queue<Position> exploration_queue;
    exploration_queue.push({start_x, start_y});
    
    processed[start_x][start_y] = true;
    group_id[start_x][start_y] = group_counter;
    group_size[group_counter] = 1;
    
    while (!exploration_queue.empty()) {
        Position current = exploration_queue.front();
        exploration_queue.pop();
        
        for (int idx = 0; idx < 4; idx++) {
            int new_x = current.x + movement[idx][0];
            int new_y = current.y + movement[idx][1];
            
            if (new_x >= 0 && new_x < width && 
                new_y >= 0 && new_y < height &&
                !processed[new_x][new_y] &&
                layout[new_x][new_y] != layout[current.x][current.y]) {
                
                processed[new_x][new_y] = true;
                group_id[new_x][new_y] = group_counter;
                group_size[group_counter]++;
                exploration_queue.push({new_x, new_y});
            }
        }
    }
}

void solve_bfs() {
    cin >> width >> height;
    
    for (int i = 0; i < width; i++) {
        cin >> layout[i];
    }
    
    group_counter = 0;
    for (int i = 0; i < width; i++) {
        for (int j = 0; j < height; j++) {
            if (!group_id[i][j]) {
                group_counter++;
                breadth_first_search(i, j);
            }
        }
    }
    
    while (height--) {
        int query_x, query_y;
        cin >> query_x >> query_y;
        cout << group_size[group_id[query_x - 1][query_y - 1]] << endl;
    }
}

int main() {
    solve_bfs();
    return 0;
}