gistfile1.cpp

#include <iostream>
#include <ciso646>
using namespace std;

#define encode(x,y) ((y)*width+(x))
#define decodex(p) ((p)%width)
#define decodey(p) ((p)/width)

int tests; 
int width,height;
int dimsum,dimprod;
bool land[90000];
int components[90000];
int lastindex, lastindexsq;
int bordersand[90000];
int islandpairminpath[360000];
int sorting[600];
int queue[360000]; 
int comefrom[90000];
int cost[90000];

void adj(int x, int y, int* array) {
    int p = encode(x,y);
    int count = 0;
    if(x>0)        array[count++] = p-1;
    if(x<width-1)  array[count++] = p+1;
    if(y>0)        array[count++] = p-width;
    if(y<height-1) array[count++] = p+width;
    array[count] = -1;
}

void dfs(int x, int y) {
    components[encode(x,y)] = lastindex;

    int as[10]; adj(x,y,as);
    for(int i=0,a; (a=as[i])>=0; i++)
        if(components[a] < 0)
            if(land[a])
                dfs(decodex(a), decodey(a));
}

void bfs(int x, int y) {
    int qfirst = 0; int qlast = 0;
    int start = encode(x,y);

    queue[qlast++] = start;
    for(int i=0; i<dimprod; i++) 
        comefrom[i] = -1;
    cost[start] = 0;

    while(qfirst < qlast){
        int current = queue[qfirst++];
        
        int as[10]; adj(decodex(current),decodey(current),as);
        for(int i=0,a; (a=as[i])>=0; i++) {
            int next = a;
            if(comefrom[next] < 0) {
                cost[next] = cost[current]+1;
                comefrom[next] = current;

                if(land[next] and components[next] != components[start]) {
                    int sg = min(components[start],components[next])*lastindex+max(components[start],components[next]);
                    islandpairminpath[sg] = min(islandpairminpath[sg], cost[next]);
                }
                if(not land[next]) {
                    queue[qlast++] = next;
                }
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin>>tests;
    while(tests-->0) {

        cin>>height>>width;
        for(int y=0; y<height; y++) {
            cin>>ws;
            for(int x=0; x<width; x++) {
                char c; cin>>c;
                land[encode(x,y)] = (c == '*');
            }
        }


        lastindex = 0;
        dimsum = width+height;
        dimprod = width*height;
        for(int i=0; i<dimprod; i++) 
            components[i] = -1;

        for(int y=0; y<height; y++) {
            for(int x=0; x<width; x++) {
                int p = encode(x,y);

                if(components[p] < 0 and land[p]) {
                    dfs(x,y);
                    lastindex++;
                }

                bool onland = false;
                int as[10]; adj(x,y,as);
                for(int i=0,a; (a=as[i])>=0; i++)
                    onland = onland or (not land[a]);
                onland = onland and land[p];
                bordersand[p] = onland;
            }
        }
        lastindexsq = lastindex*lastindex;


        for(int i=0; i<lastindexsq; i++) 
            islandpairminpath[i] = 999999999;
        for(int y=0; y<height; y++) 
            for(int x=0; x<width; x++) 
                if(bordersand[encode(x,y)])
                    bfs(x,y);


        for(int i=0; i<dimsum; i++) 
            sorting[i] = 0;
        for(int i=0; i<lastindexsq; i++) 
            if(islandpairminpath[i] < 999999999)
                sorting[islandpairminpath[i]]++;
        for(int i=0; i<dimsum; i++) 
            while(sorting[i]-->0)
                cout<<i<<' ';
        cout<<endl;
        
    }
    return 0;
}