Олимпиадная задача на bfs

INPUT.TXT
3 8
---SSS--
XX--S-X-
X-S---S-
OUTPUT.TXT
2 1 1

#include <iostream>
#include <vector>
using namespace std;
   
int arr[1001][1001];
int n, m, k = 0;
 
vector<vector<int> > types;
 
bool check(vector<int> vc){
    for(int i : vc) if(i != vc[0]) return false;
    return true;
}
void G(int i, int j){
    if(0 <= i && i < n && 0 <= j && j < m){
        if(arr[i][j]){
            types[k].push_back(arr[i][j]);
            arr[i][j] = 0;
            G(i + 1, j);
            G(i - 1, j);
            G(i, j + 1);
            G(i, j - 1);
        }
    }
}
int main() {
   char x;
   cin >> n >> m;
   types.resize(n * m);
   for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++){
            cin >> x;
            if(x == '-') arr[i][j] = 0;
            else if(x == 'S') arr[i][j] = 1;
            else if(x == 'X') arr[i][j] = 2;
        }
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++){
            if(arr[i][j]) {
                G(i, j);
                k++;
            }
        }
    int ans[] = {0, 0, 0};
    for(int i = 0; i < k; i++){
       if(check(types[i])){
           if(types[i][0] == 1) ans[0]++;
           else ans[2]++;
       } else ans[1]++;
    }
    for(int i : ans) cout << i << " ";
}

uint8_t G(int i, int j)
{
    if (i < 0 || i == n || j < 0 || j == m)
        return 0;
 
    const char x = arr[i * n + j];
    if (x == '-')
        return 0;
 
    const uint8_t res = x == 'X'? 0x1: 0x2;
    return res
        | G(i + 1, j)
        | G(i - 1, j)
        | G(i, j + 1)
        | G(i, j - 1);
}

int ans[4] = {0, 0, 0, 0};
for(int i = 0; i < n; i++)
    for(int j = 0; j < m; j++)
        ++ans[G(i, j)];

uint8_t G(int i, int j)
{
    if (i < 0 || i == n || j < 0 || j == n)
        return 0;
 
    char &x = arr[i * n + j];
    if (x == '-')
        return 0;
 
    uint8_t res = x == 'X'? 0x1: 0x2;
    x = '-';
    return res
        | G(i + 1, j)
        | G(i - 1, j)
        | G(i, j + 1)
        | G(i, j - 1);
}

int n = 3, m = 8;
char arr[] =
    "---SSS--"
    "XX--S-X-"
    "X-S---S-";
 
uint8_t G(int i, int j)
{
    if (i < 0 || i == n || j < 0 || j == m)
        return 0;
 
    char &x = arr[i * m + j];
    if (x == '-')
        return 0;
 
    uint8_t res = x == 'X'? 0x1: 0x2;
    x = '-';
    return res
        | G(i + 1, j)
        | G(i - 1, j)
        | G(i, j + 1)
        | G(i, j - 1);
}
 
int main()
{
    int ans[4] = {0, 0, 0, 0};
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            ++ans[G(i, j)];
 
    std::cout 
        << ans[2] << " "
        << ans[3] << " "
        << ans[1] << std::endl;
    return 0;
}

#include <iostream>
 
using namespace std;
 
int n, m;
char arr[1001];
 
uint8_t G(int i, int j)
{
    if (i < 0 || i == n || j < 0 || j == m)
        return 0;
 
    char &x = arr[i * m + j];
    if (x == '-')
        return 0;
 
    uint8_t res = x == 'X'? 0x1: 0x2;
    x = '-';
    return res
        | G(i + 1, j)
        | G(i - 1, j)
        | G(i, j + 1)
        | G(i, j - 1);
}
 
int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) cin >> arr[i * m + j];
    int ans[4] = {0, 0, 0, 0};
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            ans[G(i, j)]++;
 
    cout << ans[2] << " " << ans[3] << " " << ans[1];
}

int main()
{
    cin >> n >> m;
arr = new char[m * n];
    for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) cin >> arr[i * m + j];

/*тоже C++17 , если что*/
#include <sstream>
#include <iostream>
#include <map>
#include <set>
#include <algorithm>
#include <vector>
#include <string>
 
constexpr char water_char='-';
 
//тест 1
/*
static const std::string INPUT_TXT=
        "3 3\n"
        "X-X\n"
        "XXX\n"
        "X-X\n"
        ;
*/
 
//тест 2
/*
static const std::string INPUT_TXT=
        "3 8\n"
        "---SSS--\n"
        "XX--S-X-\n"
        "X-S---S-\n"
        ;
*/
 
//тест 3
static const std::string INPUT_TXT=
        "8 8\n"
        "---SSS--\n"
        "XX--S-X-\n"
        "X-S---S-\n"
        "X-------\n"
        "X-XXXXS-\n"
        "X-S---S-\n"
        "X-SXXXS-\n"
        "X-------\n"
        ;
 
 
using td_coord=uint32_t;
using td_ship_index=uint32_t;
constexpr td_ship_index ship_index_null=0;
 
struct s_ship_debug_info
{
    //координаты корабля и символ
    std::map<std::pair<td_coord/*x*/,td_coord/*y*/>,char> cells;
 
    void Append(const s_ship_debug_info& info)
    {
        if(this==&info)return;
        for(const auto& i:info.cells)
        {
            cells.emplace(i);
        }
    }
 
    void Print(const td_ship_index inx,const td_ship_index hig,const td_ship_index wid)const
    {
        std::cout<<"ship #"<<inx<<" = ";
        for(const auto& cell:cells)
        {
            std::cout<<"("<<cell.first.first<<", "<<cell.first.second<<") ";
        }
        std::cout<<'\n';
        //std::cout<<"map"<<'\n';
 
        if(cells.size())
        {
            auto [x_min,y_min]=cells.begin()->first; {}//скобки в конце поставлены для лечения моего парсера IDE,
            auto [x_max,y_max]=cells.begin()->first; {}//иначе эта строка вправо выдвигается. Если у тебя норм, то убери
 
            //ищем границы
            for(const auto& cell:cells)
            {
                x_min=std::min(x_min,cell.first.first);
                y_min=std::min(y_min,cell.first.second);
                x_max=std::max(x_max,cell.first.first);
                y_max=std::max(y_max,cell.first.second);
            }
 
            //выводим полотно
 
            //пустые линии до
            for(td_coord y=0; y<y_min; y++)
            {
                for(td_coord x=0; x<wid; x++)std::cout<<water_char;
                std::cout<<'\n';
            }
 
            //линии корабля
            for(td_coord y=y_min; y<=y_max; y++)
            {
                //пустые колонки до
                for(td_coord x=0; x<x_min; x++)std::cout<<water_char;
 
                //колонки корабля
                for(td_coord x=x_min; x<=x_max; x++)
                {
                    auto it=cells.find({x,y});
                    if(it==cells.end())
                    {
                        std::cout<<water_char;
                    }
                    else
                    {
                        std::cout<<it->second;
                    }
                }
 
                //пустые колонки после
                for(td_coord x=x_max+1; x<wid; x++)std::cout<<water_char;
                std::cout<<'\n';
            }
 
            //пустые линии после
            for(td_coord y=y_max+1; y<hig; y++)
            {
                for(td_coord x=0; x<wid; x++)std::cout<<water_char;
                std::cout<<'\n';
            }
        }
    }
};
 
int main(/*int argc, char *argv[]*/)
{
    std::istringstream ss(INPUT_TXT);
 
    auto [hig,wid]=[&ss]()
    {
        td_coord hig=0;
        td_coord wid=0;
 
        std::string hig_wid;
        std::getline(ss,hig_wid);
 
        std::istringstream hw(hig_wid);
        hw>>hig;
        hw>>wid;
 
        return std::make_pair(hig,wid);
    }();
 
    using td_ships_debug_list=std::map<td_ship_index,s_ship_debug_info>;
 
    td_ships_debug_list ships_debug_list;
 
    std::vector<td_ship_index> prev_line_scanning;
    std::vector<td_ship_index> curr_line_scanning;
 
    auto ship_index_generator=[]
    {
        static td_ship_index index=ship_index_null;
        return ++index;
    };
 
    std::string scan_line;
    uint32_t file_line_index=0;
    td_coord current_y=0;
    while(std::getline(ss,scan_line))
    {
        file_line_index++;
        if(scan_line.size()!=wid)
        {
            std::cout<<"line "<<file_line_index<<": size is not equal width "<<wid<<'\n';
            return 0;
        }
 
        curr_line_scanning.clear();
        curr_line_scanning.resize(scan_line.size(),ship_index_null);
 
        //ищем недопустимые символы
        if(scan_line.end()!=std::find_if(scan_line.begin(),scan_line.end(),[](auto& c){return c!=water_char && c!='S' && c!='X';}))
        {
            std::cout<<"line "<<file_line_index<<": wrong letters found "<<wid<<'\n';
            return 0;
        }
 
        //бежим по строке и нумеруем найденные корабли
 
        //индекс текущего в линии корабля
        std::pair<td_ship_index,bool> current_ship_index{{},false};
 
        //текущая координата x
        td_coord current_x=0;
 
        //если есть предыдущая линия - сливание касающихся кораблей
        //(более новый индекс заменяется более старым)
        auto MergeWithPrevLine=[&ships_debug_list,&prev_line_scanning,&curr_line_scanning,&current_ship_index,&current_x]
        {
            if(prev_line_scanning.size()==curr_line_scanning.size())
            {
                //если выше есть корабль
                const auto prev_ship_index=prev_line_scanning[current_x];
                if(prev_ship_index!=ship_index_null)
                {
                    //а индекс другой
 
                    if(prev_ship_index!=current_ship_index.first)
                    {
                        //то сливаем корабли, это один и тот же
 
                        //новый индекс заменяем на старый в обеих линиях
                        //(бежим до current_x включительно, дальше нет смысла)
                        for(uint32_t i=0; i<=current_x; i++)
                        {
                            if(curr_line_scanning[i]==current_ship_index.first)
                            {
                                curr_line_scanning[i]=prev_ship_index;
                            }
                            if(prev_line_scanning[i]==current_ship_index.first)
                            {
                                prev_line_scanning[i]=prev_ship_index;
 
                                //из мапы содержимое старого индекса тоже
                                //нужно перекинуть в новый индекс
                                {
                                    auto& info_to_move=ships_debug_list[current_ship_index.first];
                                    ships_debug_list[prev_ship_index].Append(info_to_move);
                                    ships_debug_list.erase(current_ship_index.first);
                                }
                            }
                        };
 
                        //текущий индекс меняем на предыдущий, будем продолжать с ним
                        current_ship_index.first=prev_ship_index;
                    }
                }
            }
        };
 
        for(auto c=scan_line.begin(); c!=scan_line.end(); c++, current_x++)
        {
            if(current_ship_index.second)
            {
                //предыдущая клетка была на корабле current_ship_index
 
                if(*c==water_char)
                {
                    //корабль current_ship_index закончился
                    current_ship_index.second=false;
                }
                else
                {
                    //корабль current_ship_index продолжается
 
                    //заполняем координату в текущей линии индексом корабля
                    curr_line_scanning[current_x]=current_ship_index.first;
 
                    //если можно, сливаем с кораблём предыдущей линии
                    MergeWithPrevLine();
                }
            }
            else
            {
                if(*c==water_char)
                {
                    //вода
                }
                else
                {
                    //новый корабль начался
                    current_ship_index=std::make_pair(ship_index_generator(),true);
 
                    //запоминаем координату на текущей линии
                    curr_line_scanning[current_x]=current_ship_index.first;
 
                    //если можно, сливаем с кораблём предыдущей линии
                    MergeWithPrevLine();
                }
            }
        }
 
        //скидываем текущую строку в ships_debug_list
        {
            if(scan_line.size()!=curr_line_scanning.size())
            {
                std::cout<<"line "<<file_line_index<<": scan_line must have same size as curr_line_scanning"<<'\n';
                return 0;
            }
 
            for(td_coord current_x=0; current_x<curr_line_scanning.size(); current_x++)
            {
                const auto c=scan_line[current_x];
                if(c==water_char)continue;
                ships_debug_list[curr_line_scanning[current_x]].cells[{current_x,current_y}]=c;
            }
        }
 
        prev_line_scanning.swap(curr_line_scanning);
        curr_line_scanning.clear();
 
        current_y++;
    }
 
    //вывод дебажной мапы с найденными кораблями
    std::cout<<"-------------------------"<<'\n';
    for(const auto& ship:ships_debug_list)
    {
        std::cout<<'\n';
        ship.second.Print(ship.first,hig,wid);
    }
 
    return 0;
}

#include <iostream>
 
int main()
{
    int n, m;
    std::cin >> n >> m;
        
    int ans[4] = {};
    
    uint8_t arr[103 + 1] = {0};
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
        {
            char ch;
            std::cin >> ch;
            if (ch == '-')
            {
                arr[j] = 0;
                continue;
            }
 
            const uint8_t x =  arr[j] | (j != 0? arr[j - 1]: 0) | (arr[j]? arr[j + 1]: 0); 
            arr[j] = x | (ch == 'S'? 0x01: 0x02);
            if (arr[j] != x)
            {
                if (x != 0 && x != 0x03)
                    --ans[x];
                                    
                ++ans[arr[j]];
            }
        }
 
    std::cout  << ans[1] << " " << ans[2] << " " << ans[3];
    return 0;
}