#include <iostream> #include <vector> #include <string> using namespace std; typedef vector<string> MyMap; void PrintMap( MyMap world) { for(auto line : world) { cout << line << endl; } cout << endl; return; } void ReadWorld(MyMap < world) { string word; cin >> word; while (cin) { world.push_back(word); cin >> word; } return; } bool FindDot(int < x, int < y, MyMap < world) { for(x=0;x<world.size();x++) { for(y=0;y<world[x].size(); y++) { if (world[x][y] == '.') { return true; } } } return false; } void Flood(MyMap < world, int x, int y, char mark) { if (x < 0 or x >= world.size() ) { // out of bounds on x; return; } if (y < 0 or y >= world[x].size()) { // out of bounds on y; return; } if (world[x][y] != '.') { // not a flood fillable spot return; } world[x][y] = mark; Flood(world, x-1,y, mark); Flood(world, x+1,y, mark); Flood(world, x,y+1, mark); Flood(world, x,y-1, mark); return; } int main() { MyMap world; ReadWorld(world); PrintMap(world); int land = 0; int x,y; while (FindDot(x,y,world)) { Flood(world, x,y, char('A'+land)); PrintMap(world); land ++; } cout << "There are " << land << " islands" << endl; return 0; }Or a little cleaner version
void Flood2(MyMap & world, int x, int y, char mark) { vector<int> xo = {-1,+1,0,0}; vector<int> yo = {0,0,-1,+1}; if (x < 0 or x >= world.size() ) { // out of bounds on x; return; } if (y < 0 or y >= world[x].size()) { // out of bounds on y; return; } if (world[x][y] != '.') { // not a flood fillable spot return; } world[x][y] = mark; for(int i=0;i<xo.size();i++) { Flood(world, x+xo[i], y+yo[i], mark); } return; }Or a little safer version
int adjust(int pos, int max) { if (pos >= max) { return 0; } if (pos <= 0) { return max-1; } } void Flood(MyMap & world, int x, int y, char mark) { x = adjust(x,world.size()); y = adjust(y,world[x].size()); vectorxo = {-1, 0, +1, -1, +1, -1, 0, +1}; vector yo = {-1,-1 ,-1, 0, 0, +1, +1, +1}; if (world[x][y] != '.') { // not a flood fillable spot return; } world[x][y] = mark; for(int i=0;i<xo.size();i++) { Flood(world, x+xo[i], y+yo[i], mark); } return; }