C++ 广度优先搜索解决瓷砖移动问题

#include #include #include using namespace std;

int main() { int w, h; cin >> h >> w; vector<vector> grid(w, vector(h)); int start_x, start_y;

// 输入矩阵
for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
        cin >> grid[j][i];
        if (grid[j][i] == '@') {
            start_x = j;
            start_y = i;
        }
    }
}

int count = 0; // 经过的黑色瓷砖数量
vector<vector<bool>> visited(w, vector<bool>(h, false)); // 记录是否已经访问过
queue<pair<int, int>> q;

// 将起始位置加入队列
q.push(make_pair(start_x, start_y));
visited[start_x][start_y] = true;

// 广度优先搜索
while (!q.empty()) {
    int x = q.front().first;
    int y = q.front().second;
    q.pop();
    
    // 判断上下左右四个相邻位置是否为黑色瓷砖，如果是且未访问过，则加入队列并记录经过的黑色瓷砖数量
    if (y > 0 && grid[x][y-1] == '.' && !visited[x][y-1]) {
        q.push(make_pair(x, y-1));
        visited[x][y-1] = true;
        count++;
    }
    if (y < h-1 && grid[x][y+1] == '.' && !visited[x][y+1]) {
        q.push(make_pair(x, y+1));
        visited[x][y+1] = true;
        count++;
    }
    if (x > 0 && grid[x-1][y] == '.' && !visited[x-1][y]) {
        q.push(make_pair(x-1, y));
        visited[x-1][y] = true;
        count++;
    }
    if (x < w-1 && grid[x+1][y] == '.' && !visited[x+1][y]) {
        q.push(make_pair(x+1, y));
        visited[x+1][y] = true;
        count++;
    }
}

cout << count << endl;

return 0;

}