首页 > 代码库 > NYOJ 598 旋转圆柱矩阵

NYOJ 598 旋转圆柱矩阵

旋转圆柱矩阵

时间限制:1000 ms  |  内存限制:65535 KB
难度:3
描述
将圆柱体的侧面展开能得到一个m*n的矩形。这是姑且看成一个01矩阵, 我们需要通过特定的移动得到另一个矩阵(该矩阵其中任意的某一列全部为1),每一次只能移动一行,且只能移动一位,可以向左移动,也可以向右移动,求最小的移动步数,如不能通过移动得到结果,则输出“-1”。
例如:
3*5的矩阵
00001
10000
00001
我们只需要将第二行向左移动一位即可得到所求。
输入
第一行一个整数N(N<=10),表示测试数据的组数。
第二行两个整数m n( 1 <= n , m <= 200),表示矩阵的行数和列数。
接下来m行,其中每一行n个数字。
输出
如果该矩阵可以移动得到结果,则每行一个数字,表示最小的移动步数。
否则输出-1。
样例输入
2
3 5 
00001
10000
00001
3 4 
0001
0100
0001
样例输出
1
2
AC码:
#include<stdio.h>
#include<string.h>
int num[205][205],sum[205];
int main()
{
	int T,n,m,a,b,i,j,min,flag;
	char str[205];
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&m);
		for(i=0;i<n;i++)
		{
			scanf("%s",str);
			flag=0;
			for(j=0;str[j]!=‘\0‘;j++)
			{
				num[i][j]=str[j]-‘0‘;
				if(num[i][j]==1)
					flag=1;
			}
		}

		if(flag==0)
		{
			printf("-1\n");
			continue;
		}
		memset(sum,0,sizeof(sum));
		for(i=0;i<n;i++)
		{
			for(j=0;j<m;j++)
			{
				if(num[i][j]==0)
				{
					a=j;
					b=j;
					while((num[i][a]==0)&&(num[i][b]==0))
					{
						a=(a+m-1)%m;
						b=(b+m+1)%m;
						sum[j]++;
					}
				}
			}
		}
		min=999999999;
		for(i=0;i<m;i++)
		{
			if(min>sum[i])
				min=sum[i];
		}
		printf("%d\n",min);
	}
	return 0;
}


NYOJ 598 旋转圆柱矩阵