学步园

题意：给定n*m（1<=n<=100 1<=m<=10000）的0-1矩阵， i 行 j 列可以通过循环移动左右的1使得当前位置为1，问要使得一列全部为1至少要移动的和

         最小值。

题解：预处理 l [][] , r [][]数组分别代表右面和左面第一个1的位置，然后得到 i j 位置满足条件的最小移动值，最后枚举得到的答案。

Sure原创，转载请注明出处

#include <iostream>
#include <cstdio>
#include <memory.h>
#define MIN(a , b) ((a) < (b) ? (a) : (b))
#define MAX(a , b) ((a) > (b) ? (a) : (b))
#define ABS(x) ((x) >= 0 ? (x) : (-(x)))
using namespace std;
const int inf = 1 << 29;
const int maxn = 110;
const int maxm = 10010;
char map[maxn][maxm];
int l[maxn][maxm],r[maxn][maxm],dp[maxn][maxm];
int m,n;
bool flag;

void read()
{
    flag = true;
    for(int i=1;i<=n;i++)
    {
        scanf("%s",map[i]+1);
        if(flag == false) continue;
        bool is = false;
        for(int j=1;j<=m;j++)
        {
            if(map[i][j] == '1')
            {
                is = true;
                l[i][m+1] = j;
                break;
            }
        }
        if(is == false)
        {
            flag = false;
            continue;
        }
        for(int j=m;j>=1;j--)
        {
            if(map[i][j] == '1')
            {
                r[i][0] = j;
                break;
            }
        }
        for(int j=1;j<=m;j++)
        {
            if(map[i][j] == '1') r[i][j] = j;
            else r[i][j] = r[i][j-1];
        }
        for(int j=m;j>=1;j--)
        {
            if(map[i][j] == '1') l[i][j] = j;
            else l[i][j] = l[i][j+1];
        }
    }
    return;
}

void solve()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int tmp = ABS(l[i][j] - j);
            dp[i][j] = MIN(tmp , m - tmp);
            tmp = ABS(r[i][j] - j);
            dp[i][j] = MIN(dp[i][j] , MIN(tmp , m - tmp));
        }
    }
    if(flag == false)
    {
        puts("-1");
        return;
    }
    int res = inf;
    for(int i=1;i<=m;i++)
    {
        int sum = 0;
        for(int j=1;j<=n;j++)
        {
            sum += dp[j][i];
        }
        res = MIN(res , sum);
    }
    printf("%d\n",res);
    return;
}

int main()
{
    while(~scanf("%d %d",&n,&m))
    {
        read();
        solve();
    }
    return 0;
}