Почему мой BFS на сетке даёт TLE, хотя алгоритм правильный?

Алгоритм верный, но константа убивает. Типичные причины на больших сетках:

1. map/set для visited вместо массива. map<pair<int,int>, int> добавляет log и огромную константу. Используйте плоский vector<int> dist(R*C, -1) с индексом r*C + c.
2. Хранение очереди из строк/пар с лишними копиями. Кодируйте клетку одним int = r*C + c.
3. Создание соседей через временный vector/tuple в каждой итерации. Лучше массивы dr[] = {0,0,1,-1}, dc[] = {1,-1,0,0}.
4. std::endl в выводе (flush каждый раз) — заменяйте на '\n'.

int dr[] = {0,0,1,-1}, dc[] = {1,-1,0,0};
vector<int> dist(R*C, -1);
queue<int> q;
dist[s] = 0; q.push(s);
while (!q.empty()) {
    int cur = q.front(); q.pop();
    int r = cur / C, c = cur % C;
    for (int k = 0; k < 4; k++) {
        int nr = r+dr[k], nc = c+dc[k];
        if (nr<0||nr>=R||nc<0||nc>=C) continue;
        int nx = nr*C + nc;
        if (dist[nx] == -1 && grid[nr][nc] != '#') {
            dist[nx] = dist[cur] + 1; q.push(nx);
        }
    }
}

Сложность остаётся O(R·C), но с маленькой константой — проходит.