A typical flood-fill algorithm application (BFS). Not very complex, except only 1 tip: instead of searching for new space, I keep all spaces(occupied or not) in a hash_map that gets updated in a flood-fill.
#include <vector> #include <stack> #include <cstdio> #include <cstdlib> #include <string> #include <cstring> #include <vector> #include <iostream> using namespace std; #include <ext/hash_map> using namespace __gnu_cxx; ///////////////////////// #define gc getchar_unlocked int read_int() { char c = gc(); while(c<'0' || c>'9') c = gc(); int ret = 0; while(c>='0' && c<='9') { ret = 10 * ret + c - 48; c = gc(); } return ret; } ///////////////////////// char map[100][100] = {0}; hash_map<int,int> hm; void clear() { memset(map, 0, 100 * 100); } int read_map(int x, int y) // returns ppl num { int ret = 0; for(int j = 0; j < y; j ++) for(int i = 0; i <= x; i ++) { char c = gc(); if(i < x) // excluding { map[j][i] = c; if(c == '*') { ret ++; } if(c != '#') { hm[j * 100 + i] = 1; } } } return ret; } int count_room(int x, int y) { int ret = 0; while(!hm.empty()) { stack<int> seeds; seeds.push(hm.begin()->first); while(!seeds.empty()) { int seed = seeds.top(); seeds.pop(); hm.erase(seed); int sx = seed % 100; int sy = seed / 100; map[sy][sx] = '#'; // <- if(sx > 0) { if(map[sy][sx-1] != '#') seeds.push(sy * 100 + sx -1); } // -> if(sx < x) { if(map[sy][sx+1] != '#') seeds.push(sy * 100 + sx +1); } // ^ if(sy > 0) { if(map[sy-1][sx] != '#') seeds.push((sy - 1) * 100 + sx); } // v if(sy < y) { if(map[sy+1][sx] != '#') seeds.push((sy + 1) * 100 + sx); } }// inner while ret ++; } return ret; } ///////////////////////// int main() { int runcnt = read_int(); while(runcnt--) { clear(); int y = read_int(); int x = read_int(); int ppl = read_map(x, y); int rcnt = count_room(x, y); printf("%.2f ", ppl*1.0/rcnt); } return 0; }