// StarryNight.c by Artur Miguel Dias/1998 #include /* maxSize=100*100, maxClusters=500, maxShapes=26, maxClusterSize=100 */ #define false 0 #define true 1 #define maxMap 100 #define maxShapes 30 typedef struct { int x, y ; } Pt ; char map[maxMap][maxMap] ; // the Map Pt size ; // the Map's size Pt minP, maxP ; // info on the current cluster int nStars ; // info on the current cluster struct { char name ; // identification of the shape Pt start[8] ; // start points for cluster comparison int nStars ; // number of stars in this shape int num ; // number of clusters with this shape (for debugging) } shapes[maxShapes] ; // arrows: the neighbourhood of each point in relative coordinates Pt arrows[] = {{ 1, 0},{ 1, 1},{ 0, 1},{-1, 1},{-1, 0},{-1,-1},{ 0,-1},{ 1,-1}} ; #define set(p,n) ( map[p.y][p.x] = n ) int get(Pt p) { if( p.x < 0 || p.x >= size.x || p.y < 0 || p.y >= size.y ) return '0' ; else return map[p.y][p.x] ; } // Walks one unit in the direction "arrow" using the co-ordinate // system represented by "rotSym". The values of "rotSym" range from 0 to 7 // and have the following meanings: // 0=0 1=90 1=180 3=270 4=0s 5=90s 6=180s 7=270s // For example 7 represents a 270 rotation followed by a symetry. Pt Walk(Pt p, int arrow, int rotSym) { Pt res ; if( arrow == -1 ) return p ; arrow = (arrow + 2 * (rotSym%4)) % 8 ; if( rotSym / 4 == 0 ) { res.x = p.x + arrows[arrow].x ; res.y = p.y + arrows[arrow].y ; } else { res.x = p.x + arrows[arrow].y ; res.y = p.y + arrows[arrow].x ; } return res ; } void LoadMap(char *fname) { FILE *f ; int i ; if( (f = fopen(fname, "r")) == NULL ) exit( 1 ) ; fscanf(f,"%d", &size.x) ; fscanf(f,"%d", &size.y) ; fgets(map[0], 1000, f) ; // skip nl for( i = 0 ; i < size.y ; i++) fgets(map[i], 1000, f) ; } void WriteMap(char *fname) { FILE *f ; Pt p ; if( (f = fopen(fname, "w")) == NULL ) exit( 1 ) ; for( p.y = 0 ; p.y < size.y ; p.y++ ) { for( p.x = 0 ; p.x < size.x ; p.x++ ) fputc(get(p), f) ; fputc('\n', f) ; } } // Determinates the enclosing rectangle of the current cluster void UpdateMinMax(Pt p) { nStars++ ; if( p.x < minP.x ) minP.x = p.x ; if( p.x > maxP.x ) maxP.x = p.x ; if( p.y < minP.y ) minP.y = p.y ; if( p.y > maxP.y ) maxP.y = p.y ; } // Fills a cluster with the char "name" (for the first time) void FirstFill(Pt p, int arrow, int name) { int a ; Pt np = Walk(p, arrow, 0) ; if( get(np) != '0' && get(np) != name ) { set(np, name) ; UpdateMinMax(np) ; for( a = 0 ; a < 8 ; a++ ) FirstFill(np, a, name) ; } } // Fills a cluster with the char "name" void Fill(Pt p, int arrow, int name) { int a ; Pt np = Walk(p, arrow, 0) ; if( get(np) != '0' && get(np) != name ) { set(np, name) ; for( a = 0 ; a < 8 ; a++ ) Fill(np, a, name) ; } } // Determines the start point where the comparison of the current cluster must begin // for the orientation "rotSym" Pt StartPt(int rotSym, int name) { Pt p = Walk(minP, 1, rotSym) ; Pt res = minP ; if( p.x < minP.x ) res.x = maxP.x ; if( p.y < minP.y ) res.y = maxP.y ; while( get(res) != name ) res = Walk(res, 0, rotSym) ; return res ; } // Compares two clusters according to the orientation "rotSym" int CompareX(Pt p, Pt q, int arrow, int rotSym) { int a ; Pt np = Walk(p, arrow, 0), nq = Walk(q, arrow, rotSym) ; if( get(np) == '0' ) return get(nq) == '0' ; if( get(np) == '1' ) return true ; set(np, '1') ; if( get(nq) == '0' ) return false ; for( a = 0 ; a < 8 ; a++ ) if( !CompareX(np, nq, a, rotSym) ) return false ; return true ; } // Compares the cluster starting at "p" with the cluster with starting points "start" int Compare(Pt p, Pt start[], int old) { int rotSym ; for( rotSym = 0 ; rotSym < 8 ; rotSym++ ) { if( CompareX(p, start[rotSym], -1, rotSym) ) return true ; else Fill(p, -1, old) ; } return false ; } // Scans the map, finds the clusters, paints them void ProcessMap() { Pt p ; int k, rotSym ; int nShapes = 0 ; char name = 'a' ; for( p.y = 0 ; p.y < size.y ; p.y++ ) for( p.x = 0 ; p.x < size.x ; p.x++ ) { if( get(p) == '1' ) { minP = maxP = p ; nStars = 0 ; FirstFill(p, -1, name) ; for( k = 0 ; k < nShapes ; k++ ) if( shapes[k].nStars == nStars && Compare(p, shapes[k].start, name) ) { // Same shape shapes[k].num++ ; Fill(p, -1, shapes[k].name) ; goto next ; } // New shape if( nShapes == maxShapes ) { fprintf(stderr, "Too many shapes") ; getchar() ; exit(1) ; } shapes[nShapes].name = name ; shapes[nShapes].nStars = nStars ; shapes[nShapes].num = 1 ; for( rotSym = 0 ; rotSym < 8 ; rotSym++ ) shapes[nShapes].start[rotSym] = StartPt(rotSym, name) ; nShapes++ ; name++ ; } next: ; } // for( k = 0 ; k < nShapes ; k++ ) // printf("%c = %d\n", shapes[k].name, shapes[k].num) ; } main() { LoadMap("STARRY.IN") ; ProcessMap() ; WriteMap("STARRY.OUT") ; }