我要啦免费统计
#include <stdio.h>
#include 
<stdlib.h>
#include 
<assert.h>

#define NAME "starry"
/* MAXSTAR is the largest a cluster can be */
#define MAXSTAR 160

/* the board */
char board[100][100];
int w, h;

/* clusters already lettered */
int stars[26][MAXSTAR]; /* stars are stored as xval + yval*1000 */
int count[26]; /* number of stars */
int size[26][2]; /* the x & y dimensions */
int nstart; /* number of clusters */

/* the current cluster */
int current[MAXSTAR][2]; /* y, x */
int ncurrent; /* number of stars in current cluster */

/* int_comp is integer comparison, used for bsearch and qsort */
int
int_comp(
const void *pa, const void *pb)
 {
  
int a = *(int*)pa;
  
int b = *(int*)pb;
  
if (a > b) return 1;
  
else if (a < b) return -1;
  
else return 0;
 }

/* find the boundary (in my,mx,My, and Mx.. m is minimum, M is maximum */
/* also fills in current */
int
find_boundary(
int y, int x, int *my, int *mx, int *My, int *Mx)
 {
  
int rv = 0;
  
if (board[y][x] != '1'return 0/* not a star or already visited */
  rv
++/* one more star */
  board[y][x] 
= '2'/* mark as visited */

  
/* put in current cluster */
  current[ncurrent][
0= y;
  current[ncurrent][
1= x;
  ncurrent
++;

  
/* update boundary */
  
if (y < *my) *my = y;
  
if (y > *My) *My = y;
  
if (x < *mx) *mx = x;
  
if (x > *Mx) *Mx = x;

  
/* check all adjacent stars */
  
if (x > 0
   {
    x
--;
    rv 
+= find_boundary(y, x, my, mx, My, Mx);
    
if (y > 0) rv += find_boundary(y-1, x, my, mx, My, Mx);
    
if (y+1 < h) rv += find_boundary(y+1, x, my, mx, My, Mx);
    x
++;
   }
  
if (y > 0) rv += find_boundary(y-1, x, my, mx, My, Mx);
  
if (y+1 < h) rv += find_boundary(y+1, x, my, mx, My, Mx);
  
if (x+1 < w)
   {
    x
++;
    rv 
+= find_boundary(y, x, my, mx, My, Mx);
    
if (y > 0) rv += find_boundary(y-1, x, my, mx, My, Mx);
    
if (y+1 < h) rv += find_boundary(y+1, x, my, mx, My, Mx);
    x
--;
   }
  
return rv;
 }

/* this is a very basic flood fillfill ch everywhere there's not a '0' */
void
mark_shape(
int y, int x, char ch)
 {
  
if (board[y][x] == ch) return/* done already */
  
if (board[y][x] == '0'return/* nothing to do */

  board[y][x] 
= ch;

  
/* recurse on all boundary stars */
  
if (x > 0
   {
    x
--;
    mark_shape(y, x, ch);
    
if (y > 0) mark_shape(y-1, x, ch);
    
if (y+1 < h) mark_shape(y+1, x, ch);
    x
++;
   }
  
if (y > 0) mark_shape(y-1, x, ch);
  
if (y+1 < h) mark_shape(y+1, x, ch);
  
if (x+1 < w) 
   {
    x
++;
    mark_shape(y, x, ch);
    
if (y > 0) mark_shape(y-1, x, ch);
    
if (y+1 < h) mark_shape(y+1, x, ch);
   }
 }

/* is shape id the same as the current shape */
/* specify the orientation with dy/dx and by/bx */
/* dy/dx is the difference value to associate with y and x changes */
/* by/bx is the upper right corner of the bounding box with respect
   to the current orientation 
*/
/* NOTE: assumes that the number of stars are the same */
int
check_shape(
int id, int dy, int dx, int by, int bx)
 {
  
int lv;
  
int pval;

  
for (lv = 0; lv < ncurrent; lv++)
   {
    pval 
= (current[lv][0]-by)*dy + (current[lv][1]-bx)*dx;
    
if (!bsearch(&pval, stars[id], count[id], sizeof(stars[id][0]), int_comp))
      
return 0/* found a star that didn't match */
   }
  
return 1;
 }

/* we found a star here, make it a cluster */
void
fix_board(
int y, int x)
 {
  
int mx, my, Mx, My;
  
int cnt;
  
int lv;
  
int pw, ph;
  
int f;

/* gather the cluster information */
  mx 
= Mx = x;
  my 
= My = y;

  ncurrent 
= 0;
  cnt 
= find_boundary(y, x, &my, &mx, &My, &Mx);

  pw 
= Mx - mx + 1;
  ph 
= My - my + 1;

  f 
= 0;
  
/* check each cluster */
  
for (lv = 0; lv < nstart; lv++)
    
if (cnt == count[lv]) /* the cluster must have the same # of stars */
     {
      
if (pw == size[lv][1&& ph == size[lv][0])
       { 
/* the bounding box sizes match */
 f 
+= check_shape(lv, 10001, my, mx);
 f 
+= check_shape(lv, 1000-1, my, Mx);
 f 
+= check_shape(lv, -10001, My, mx);
 f 
+= check_shape(lv, -1000-1, My, Mx);
       }
      
if (pw == size[lv][0&& ph == size[lv][1])
       { 
/* the bounding box sizes match */
 f 
+= check_shape(lv, 11000, my, mx);
 f 
+= check_shape(lv, 1-1000, my, Mx);
 f 
+= check_shape(lv, -11000, My, mx);
 f 
+= check_shape(lv, -1-1000, My, Mx);
       }
      
if (f) break;
     }
  
if (f) mark_shape(y, x, 'a' + lv); /* found match */
  
else { /* new cluster! */
    count[nstart] 
= 0;
    mark_shape(y, x, 
'a' + nstart);
    
for (lv = 0; lv < ncurrent; lv++)
      stars[nstart][lv] 
= (current[lv][0]-my)*1000 + (current[lv][1]-mx);
    count[nstart] 
= ncurrent;
    
/* we need the stars in increasing order */
    qsort(stars[nstart], count[nstart], 
sizeof(stars[nstart][0]), int_comp);
    size[nstart][
0= ph;
    size[nstart][
1= pw;
    nstart
++;
   }
 }

int
main(
int argc, char **argv)
 {
  
//FILE *fin, *fout;
  int lv, lv2;

  
//fin = fopen(NAME ".in", "r");
  
//fout = fopen(NAME ".out", "w");
  
//assert(fin);
 
// assert(fout);

/* read in the data */
  scanf (
"%d %d"&w, &h);

  
for (lv = 0; lv < h; lv++) scanf ("%s", board[lv]);
 
// fclose(fin);

/* everywhere there's a star not in a cluster, make it into one */
  
for (lv = 0; lv < h; lv++)
    
for (lv2 = 0; lv2 < w; lv2++)
      
if (board[lv][lv2] == '1')
        fix_board(lv, lv2);

/* output data */
  
for (lv = 0; lv < h; lv++)
   {
    printf (
"%c", board[lv][0]);
    
for (lv2 = 1; lv2 < w; lv2++)
      printf (
"%c", board[lv][lv2]);
     printf ( 
"\n");
   }

 
// fclose(fout);
  return 0;
 }


修改 usaco 分析的代码
floodfill找出1的区域  在和以前找出的区域 旋转匹配 如果找到则用前面那个编号 找不到则编号加1

posted on 2008-10-11 15:58 阅读(392) 评论(0)  编辑 收藏 引用 所属分类: pku

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理