Значит, алгоритм может быть рабочий. Но тогда как проверять сохранение связности? Не могу понять, каким образом эту задачу решает функция
checkConsistency. Вот все функции, упомянутые TheFire & theShockwave, на C#.
checkConsistencyКод:
private bool checkConsistency(int [,] m){
int [,] tmp=new int[3,3];
int bi=-1,bj=-1;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
if((tmp[i,j]=m[i,j])==1 && (i!=1||j!=1) ){bi=i;bj=j;}
}
}
tmp[1,1]=0;
if(bi!=-1){
Queue q=new Queue(16);
q.Enqueue(bi);
q.Enqueue(bj);
int i,j;
while(q.Count!=0) {
i=System.Convert.ToInt32(q.Dequeue));
j=System.Convert.ToInt32(q.Dequeue));
tmp[i,j]=0;
if((i!=0)&&(j!=0)&&(tmp[i-1,j-1]==1)) {
q.Enqueue(i-1);q.Enqueue(j-1);
}
if(i!=0&&tmp[i-1,j]==1) {
q.Enqueue(i-1);q.Enqueue(j);
}
if(i!=0&&j!=2&&tmp[i-1,j+1]==1) {
q.Enqueue(i-1);q.Enqueue(j+1);
}
if(j!=0&&tmp[i,j-1]==1) {
q.Enqueue(i);q.Enqueue(j-1);
}
if(j!=2&&tmp[i,j+1]==1) {
q.Enqueue(i);q.Enqueue(j+1);
}
if(i!=2&&j!=0&&tmp[i+1,j-1]==1) {
q.Enqueue(i+1);q.Enqueue(j-1);
}
if(i!=2&&tmp[i+1,j]==1) {
q.Enqueue(i+1);q.Enqueue(j);
}
if(i!=2&&j!=2&&tmp[i+1,j+1]==1) {
q.Enqueue(i+1);q.Enqueue(j+1);
}
}
bi=-1;bj=-1;
for(i=0;i<3;i++){
for(j=0;j<3;j++){
if(tmp[i,j]==1 && (i!=1||j!=1) ){bi=i;bj=j;}
}
}
if(bi!=-1) return false;
else return true;
}else{
return true;
}
}
skeletonLetterКод:
private void skeletonLetter(ref Bitmap bmp){
int i=1,j=1,width=bmp.Width,height=bmp.Height;
int [,]bitmap=new int[width+2,height+2];
for(i=2;i<width;i++){
for(j=2;j<height;j++){
if(bmp.GetPixel(i-1,j-1).GetBrightness()==0) bitmap[i,j]=1;
else bitmap[i,j]=0;
}
}
int [,]okr=new int[3,3];
int []okrs=new int[10];
bool flag=true;
while(flag){
flag=false;
for(i=1;i<=width;i++){
for(j=1;j<=height;j++){
if(bitmap[i,j]==1){
okr[0,0]=okrs[0]=bitmap[i-1,j-1];
okr[1,0]=okrs[1]=bitmap[i,j-1];
okr[2,0]=okrs[2]=bitmap[i+1,j-1];
okr[2,1]=okrs[3]=bitmap[i+1,j];
okr[2,2]=okrs[4]=bitmap[i+1,j+1];
okr[1,2]=okrs[5]=bitmap[i,j+1];
okr[0,2]=okrs[6]=bitmap[i-1,j+1];
okr[0,1]=okrs[7]=bitmap[i-1,j];
okrs[8]=okrs[0];
okrs[9]=okrs[1];
if(pointB(ref okrs)>1 && point03(okrs) && checkConsistency(okr)){
bitmap[i,j]=2;
//MessageBox.Show(i.ToString()+" "+j.ToString());
}
}
}
}
for(i=1;i<=width;i++){
for(j=1;j<=height;j++){
if(bitmap[i,j]==2){
bitmap[i,j]=0;
flag=true;
}
}
}
}
for(i=1;i<=width-1;i++) {
for(j=1;j<=height-1;j++) {
if(bitmap[i,j]==1) bmp.SetPixel(i-1,j-1,Color.Black);
else bmp.SetPixel(i-1,j-1,Color.White);
}
}
}
point03Код:
private bool point03(int []m){
for(int i=0;i<8;i++){
if(m[i]==0 && m[i+1]==0 && m[i+2]==0){
return true;
}
}
return false;
}
pointBКод:
private int pointB(ref int [] m) {
int sum=0;
for(int i=0;i<8;i++){
if(m[i]!=0) sum++;
}
return sum;
}
