SPOJ #691. Hotel Floors

#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 \n
        {
            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\n", ppl*1.0/rcnt);
    }

    return 0;
}