金币问题.cpp

经典的金币问题的实现。并进行了优化。有详细的注释。

#include<stdio.h>
#include<string.h>

int a[101][101];		//存储初始状态
int b[101][101];		//存储目标状态
int row[101];			//存储目标状态每一行的和
int s[101];				//调整列用到的状态数组
int n,m;				//n 行   m 列
int MinMv;				//最小调整次数
int rowOk(int i)		
{			
	int sum=0,c1=0,c2=0;
	for(int j=1;j<=m;++j)	
		sum += a[i][j];	
	if(sum == row[i]) 
		c1 = 1;
	if(m - sum == row[i]) 
		c2 = 2;
	return c1+c2;
}

int Find(int pos)		//调整列，仔细读这个函数，就这个函数可能读起来有难度
{
	int now;						
	for(int j=pos;j<=m;++j)
	{
		now = s[j] ? s[j]:j;
		for(int i=1;i<=n;++i)
		{
			if(b[i][pos] != a[i][now])
				break;
		}
		if(i > n)
		{
			s[j] = s[pos] ? s[pos]:pos;
			if(j == pos) return 0;
			else         return 1;
		}
	}
	return -1;
}

void DoWithRow(int row)		//对行执行翻转操作
{				
	for(int j=1;j<=m;++j)	
		a[row][j] = 1 - a[row][j];	
}

void DFS(int i,int cnt)		//i：第i行；cnt：目前执行的操作数目
{				
	if(i > n)
	{
		memset(s,0,sizeof(s));
		for(int j=1;j<=m;++j)
		{
			int findrow = Find(j);
			if(findrow!=-1)
				cnt += findrow;
		}
		if(MinMv > cnt) 		
			MinMv = cnt;		
	}
	else
	{
		switch(rowOk(i))		//这里面根据行的状态进行了必要的剪枝
		{
		case 0:
			return;
		case 1:
			DFS(i+1,cnt);break;
		case 2:
			DoWithRow(i);
			DFS(i+1,cnt+1);break;
		default:
			DFS(i+1,cnt);
			DoWithRow(i);
			DFS(i+1,cnt+1);
			DoWithRow(i);	
		}
	}
	return;
}

int main()
{
	int i,j;				
	MinMv=65535;
    memset(row,0,sizeof(row));
	printf("Please input the row and colum(like a,b): ");
  	scanf("%d,%d",&n,&m);
	printf("Please input the initial one and target one: \n");
	for(i=1;i<=2*n;++i)
	{
		if(i <= n)
		{
			for(j=1;j<=m;++j) 
				scanf("%d",&a[i][j]);
			
		}
		else 
		{
			for(j=1;j<=m;++j)
			{				
				scanf("%d",&b[i-n][j]);
				row[i-n] += b[i-n][j];
			}
		}		
	}
	DFS(1,0);  
    if(MinMv == 65535)
		printf("%d\n",-1);
	else
		printf("The minmum of moveing is: %d\n",MinMv);		 
	return 0;
}