Codeforces 230C Shifts（模拟+展开字符串）

分手后的思念是犯贱 2022-06-13 10:27 181阅读 0赞

Description

You are given a table consisting of *n* rows and *m* columns. Each cell of the table contains a number, 0 or 1. In one move we can choose some row of the table and cyclically shift its values either one cell to the left, or one cell to the right.

To cyclically shift a table row one cell to the right means to move the value of each cell, except for the last one, to the right neighboring cell, and to move the value of the last cell to the first cell. A cyclical shift of a row to the left is performed similarly, but in the other direction. For example, if we cyclically shift a row "00110" one cell to the right, we get a row "00011", but if we shift a row "00110" one cell to the left, we get a row "01100".

Determine the minimum number of moves needed to make some table column consist only of numbers 1.

Input

The first line contains two space-separated integers: *n* (1 ≤ *n* ≤ 100) — the number of rows in the table and *m* (1 ≤ *m* ≤ 104) — the number of columns in the table. Then *n* lines follow, each of them contains *m* characters "0" or "1": the *j*\-th character of the *i*\-th line describes the contents of the cell in the *i*\-th row and in the *j*\-th column of the table.

It is guaranteed that the description of the table contains no other characters besides "0" and "1".

Output

Print a single number: the minimum number of moves needed to get only numbers 1 in some column of the table. If this is impossible, print -1.

Sample Input

Input

3 6
    101010
    000100
    100000

Output

Input

2 3
    111
    000

Output

-1

题意：

推桌子每次只能推一格，注意是循环的，从第一个到最后一个只要推一下，使得有一列全为1，输出最小步数

题解：

感觉不是很难的一题，可是超时了n次，思路很简单就是模拟，有展开字符串的思想，如果不是每一行最后一个‘1’的位置就取当前的1的位置和下一个1的位置中间的节点求与两点的最短距离，累加到每一列的数组中，如果是最后一个就展开字符串，与每一行第一个1的位置做最短距离求，然后累加，扫描所有行，最后取数组中最小的就是答案

代码：

#include<stdio.h>
    #include<cstring>
    #include<string>
    #include<iostream>
    #include<algorithm>
    #include<math.h>
    #include<queue>
    #include<stack>
    using namespace std;
    int p[105][10005];//用于储存图...感觉可以不要
    int b[105];//用与储存每行有多少个‘1’
    int a[105][10005];//第‘i’行记录‘1’的位置
    int h[10005];//用于储存每一列累加最小距离和
    int main()
    {
        int m,n,i,j,k,tag,flag,minn,num;
        while(scanf("%d%d",&m,&n)!=EOF)
        {
            flag=1;
            for(i=0;i<m;i++)
            {
                b[i]=0;
                tag=0;
                for(j=0;j<n;j++)
                {
                    scanf("%1d",&p[i][j]);
                    if(p[i][j]==1)
                    {
                        a[i][b[i]]=j;
                        b[i]++;
                        tag=1;
                    }
                }
                if(!tag)
                    flag=0;
            }
            if(!flag)
            {
                printf("-1\n");//如果一行没有出现1则就不存在
                continue;
            }
            for(i=0;i<n;i++)
                h[i]=0;//初始化每行
            for(i=0;i<m;i++)
            {
                for(j=0;j<b[i];j++)
                {
                    if(j==b[i]-1)//展开字符串的思想分情况
                    {
                        for(k=a[i][j];k<=n+a[i][0];k++)
                        {
                            if(k<n)
                            {
                                h[k]+=min(abs(k-a[i][j]),abs(k-n-a[i][0]));
                            }
                            else
                            {
                                h[k%n]+=min(abs(k-a[i][j]),abs(k-n-a[i][0]));
                            }
                        }
                    }
                    else
                    {
                        for(k=a[i][j];k<=a[i][j+1];k++)
                        {
                            h[k]+=min(abs(k-a[i][j]),abs(k-a[i][j+1]));
                        }
                    }
                }
            }
            minn=10086111;
            for(i=0;i<n;i++)//扫一遍求最小值
            {
                if(minn>h[i])
                    minn=h[i];
            }
            printf("%d\n",minn);
        }
        return 0;
    }