|
|
细菌繁殖的题目 [所有相关帖子]细菌繁殖的题目要求：
在一个800*600的棋盘中播种一个细菌，然后这个细菌开始繁殖。如果这个细菌的周围（8个方向）有地方适合他生存，则使该地方带菌，如此类推。
细菌的繁殖是有方向顺序的，最优先右方，然后优先级逆时针递减。也就是如果右面可以繁殖，繁殖右面，不可以就右上方，如果还不可以就上方、左上方。。。
细菌繁殖一次后，要等到它的子孙都不繁殖后才会继续繁殖，
求最后一个繁殖的细菌所在的位置。
 #include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <memory.h>
#define WIDTH 800 //the map's width
#define HEIGHT 600 //the map's height
int map[WIDTH][HEIGHT]; //map,mark the path use integer
  char to[8][2]= {1,0, 1,-1, 0,-1, -1,-1, -1,0, -1,1, 0,1, 1,1};// eight ways
typedef struct _pos
{
 unsigned x: 12;
unsigned y: 12;
unsigned way: 3;
 }POS;//define a position,x is row number and y is column number,way is which way to go.
POS path[WIDTH*HEIGHT];// the path
char check(int x,int y) //check the next position(be out or have past)
{
if(x<0 || x>=WIDTH || y<0 || y>=HEIGHT || map[x][y])
return 1;//invalid
return 0;//valid
}
void main()
{
int pos=0,cnt=1;//pos is the current position,cnt is the count of position having past.
srand((unsigned)time(0));
  POS last,first={rand()%WIDTH,rand()%HEIGHT,0};//the last and first position
memset(map,0,sizeof(map)); //clear
memset(path,0,sizeof(path));//clear
path[0]=first; //at first
map[path[0].x][path[0].y] = 1;//pass number
while(1)
{
for(int i=path[pos].way;i<8;i++)//8 ways
{
if(!check(path[pos].x+to[i][0],path[pos].y+to[i][1]))
{
path[pos].way = i; //register the way having past
pos++;
path[pos].x = path[pos-1].x+to[i][0];
path[pos].y = path[pos-1].y+to[i][1];
map[path[pos].x][path[pos].y] = cnt+1;
last=path[pos]; //note the last
cnt++; //count
i=0xffff;
break;
 }
}
if(cnt>=WIDTH*HEIGHT)
break;//finished
if(i<0xffff)
pos--;//run back
printf("step %d : (%d,%d) pos=%d ",cnt-1,path[pos-1].x,path[pos-1].y,pos);
}
if(WIDTH<=28 && HEIGHT<=20 ) //too big number is not fit for print the map
{
for(int k=0;k<HEIGHT;k++)
{
for(int i=0;i<WIDTH;i++)
{
printf("%3d ",map[i][k]);
}
printf(" ");
}
}
printf(" the last is (%d,%d) ",last.x,last.y);//show the last
}
|