cb1.cpp

求最小棋盘的算法原代码

#include <stdio.h>
#include <math.h>
#include <stdlib.h>   
#include <stdio.h>   
#define max 100

int m,n,p,q,i,a=0,b=0,wod=0,emp=1,x=0,y=0,hang=1;
int outfile[max][max]={0,0},lie[100];//lie队列保存棋子确定顺序
int aa[100],bb[100];//用以记录棋子坐标
int maxa,maxb;//用于记录棋盘大小

void main()
{
	FILE *in,*out;
	int done=0,,lastouta,lastoutb=0;//lastout用来记录前一个确定位置的棋子位置
	char infile[10],ch,mid[100][100],putout[10];
	void diyihang(int x1,int y1);
	int ensureline(int x2,int y2);
	printf("Enter the infile name:\n");
    scanf("%s",infile);
	if((in=fopen(infile,"r"))==NULL)
	{
		printf("cannot open infile\n");
	}
	ch=fgetc(in);
	while(ch!=' '&&ch!='\n')
	{
		ch=fgetc(in);
	}
	while(!feof(in))
	{
		if(ch!=' '&&ch!='\n')
		{
			wod=wod+1;
		}
		ch=fgetc(in);
	}
	wod=sqrt(wod);
    fclose(in);
	in=fopen(infile,"r");
	ch=fgetc(in);
	while(ch!=' '&&ch!='\n')
	{
		ch=fgetc(in);
	}
	while(!feof(in))
	{
		if(b<wod)
		{
			if(ch=='1'||ch=='0')
			{
				mid[a][b]=ch;
				b++;
			}
		}
		else
		{
			b=0;
			a++;
		}
		ch=fgetc(in);
	}
	a=0,b=0;
	outfile[x][y]=b+1;
	maxa=x;
	maxb=y;
	printf("%d,%d,%d",x,y,b+1);
	lie[emp]=b+1;
	aa[b+1]=x;
	bb[b+1]=y;
	lastoutb=b;
	lastouta=x;
	b++;
	ch=mid[a][b];
	while(b<wod)
	{
		if(ch=='1')//判断是否相容
		{
			if(mid[lastoutb][b]=='1')//判断与前一个进入棋盘的棋子是否相容
			{
				y++;
				diyihang(x,y);
			}
			else
			{
				lastouta++;
				diyihang(lastouta,a);
			}
		}
		else
		{
			b++;
			ch=mid[a][b];
		}
	}
	hang++;
	while(hang<wod)
	{
		a=lie[hang]-1;
		b=1;
		ch=mid[a][b];
		while(b<wod)
		{
			if(ch!='0'&&b!=a)
			{
				for(i=1;i<=emp;)//检索该棋子是否已确定位置
				{
					if(b==lie[i]-1)
					{
						done=1;//表示已确定过
						break;
					}
					i++;
				}
				if(done==0)//还未确定
				{
					m=aa[a+1];
					for(n=0;n<=emp;)//检索同一行是否有冲突
					{
						if(outfile[m][n]>0)
						{
							if(mid[(outfile[m][n]-1)][b]=='0')
							break;
						}
						n++;
					}
					if(n>emp)//行无冲突
					{
						for(q=bb[a+1]+1;q<emp;)//找到没有冲突的列
						{
							for(p=0;p<m;)
							{
								if(outfile[p][q]>0)
								{
									if(mid[(outfile[p][q])-1][b]=='0')
									break;
								}
								p++;
							}
							if(p==m)
							{
								break;
							}
							q++;
						}
						p=ensureline(p,n);
						if(outfile[p][q]>0)
						{
							q=q+1;
						}
						outfile[p][q]=b+1;
						if(p>maxa)
						{
							maxa=p;
						}
						if(q>maxb)
						{
							maxb=q;
						}
						emp++;
						lie[emp]=b+1;
						aa[b+1]=p;
						bb[b+1]=q;
						printf("%d,%d,%d",p,q,b+1);
					}
					else//行有冲突，所以能确定列
					{
						n=bb[a+1];
						m=ensureline(m,q);
						if(outfile[m][n]>0)
						{
							m=m+1;
						}
						outfile[m][n]=b+1;
						if(m>maxa)
						{
							maxa=m;
						}
						if(n>maxb)
						{
							maxb=n;
						}
						emp++;
						lie[emp]=b+1;
						aa[b+1]=m;
						bb[b+1]=n;
						printf("%d,%d,%d",m,n,b+1);
					}
				}
				b++;
				ch=mid[a][b];
				done=0;
			}
			else
			{
				b++;
				ch=mid[a][b];
				done=0;
			}
		}
		hang++;
	}
	printf("Enter the outfile name:\n");
	scanf("%s",putout);
	if((out=fopen(putout,"w"))==NULL)
	{
		printf("cannot open outfile\n");
	}
	printf("%d,%d\n",maxa+1,maxb+1);
	for(m=0;m<maxa+1;)//输出至屏幕
	{
		for(n=0;n<maxb+1;)
		{
			printf("%d",outfile[m][n]);
			n++;
		}
		printf("\n");
		m++;
	}
	for(hang=1;hang<=emp;)//输出至文本
	{
		ch=char(aa[hang]+48);
		fputc(ch,out);
		ch=' ';
		fputc(ch,out);
		ch=char(bb[hang]+48);
		fputc(ch,out);
		fprintf(out,"\r\n");
		hang++;
	}
	fclose(in);
	fclose(out);
}

void diyihang(int x1,int y1)//处理矩阵第一行
{
	emp++;//记录已确定位置棋子数
	outfile[x1][y1]=b+1;
	if(x1>maxa)
	{
		maxa=x1;
	}
	if(y1>maxb)
	{
		maxb=y1;
	}
	printf("%d,%d,%d",x1,y1,b+1);
	lie[emp]=b+1;
	aa[b+1]=x1;
	bb[b+1]=y1;
	if(lastoutb==0)
	{
		lastoutb=b;	
	}
	b++;
	ch=mid[a][b];
}

int ensureline(int x2,int y2)//已确认列，再次确认无行冲突的行
{
	for(y2=0;y2<emp;)
	{
		if(outfile[x2][y2]>0)
		{
			if(mid[(outfile[x2][y2])-1][b]=='0')
			{
				x2++;
				y2=0;
			}
			else 
			{
				y2++;
			}
		}
		else 
		{
			y2++;
		}
	}
	return x2;
}