Hungry Rabbit | 兔子

Problem C. Hungry Rabbit

Input file: hungry.in

Output file: hungry.out

Time limit: 10 seconds

Memory limit: 512 megabytes

可怕的洪水在夏天不期而至，兔子王国遭遇了前所未有的饥荒，它们不得不去外面的森林里寻找食物。

为了简化起见，我们假设兔子王国中有 n 只兔子，编号为 1 − n。在救济粮到来之前的 m 天中，每天恰好有 k 只兔子需要去森林里寻找粮食。森林里居住着可怕的大灰狼，所幸兔子已经摸清了大灰狼捕食习惯，即狼们在每一天只会捕食特定编号的兔子。为了安全起见，兔子们需要保证每次出去觅食的 k 只兔子都不会被狼捕食。

由于每天出去捕食的兔子都不尽相同，它们为每一天定义了一个生疏度 pi ，即第 i 天出来寻找食物，但是第 i − 1天却没有出来觅食的兔子个数。规定第1天的生疏度为 0.

现在兔子们希望在保证安全的前提下，每天的生疏度不能超过l，请为兔子们构造一个合法的方案。

Input

第一行包括四个整数 n, m, k 和l.

接下来n行，每行一个长度为m的01串。其中第i 行第j 个字符若为0，则表示狼在第j 天会捕食编号为 i 的兔子，为 1则表示不捕食。

Output

m 行，每行 k 个 1 − n 之间互不相同的整数，代表这一天出去寻找食物的兔子编号。如果没有合法方案，则输出一行−1即可。

Sample input.

5 4 3 1

1001

1101

1111

1110

0111

Sample output.

2 3 4

3 4 5

2 3 5

对于样例，在这4天中，出去觅食的兔子集合分别为 {2, 3, 4}, {2, 3, 4}, {3, 4, 5}, {2, 3, 5}.

• 对于 20%的测试数据，1 ≤ n,m ≤ 10

• 对于 100% 的测试数据，1 ≤ n,m ≤ 800, 1 ≤ k ≤ n, 1 ≤ l ≤ k

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 const int N=;

 int n,m,k,l;

 int maxl[N][N],id[N];

 bool flag[N][N];

 int day;

 inline bool cmp(const int &a, const int &b) {

     return maxl[a][day]>maxl[b][day];

 }

 int main() {

   //  freopen("hungry.in", "r", stdin);

   //  freopen("hungry.out", "w", stdout);

     scanf("%d%d%d%d",&n,&m,&k,&l);

     for(int i=;i<=n;i++) {

         char s[N];

         scanf("%s",s+);

         for(int j=m;j;j--)

           if(s[j]=='')

             maxl[i][j]=;

           else

             maxl[i][j]=maxl[i][j+]+;

         id[i]=i;

     }

     day=;

     sort(id+,id+n+,cmp);

     for(int i=;i<=k;i++)

       flag[day][id[i]]=;

     for(int i=;i<=m;i++){

       for(int j=;j<=n;j++)

         flag[i][j]=flag[i-][j];

         day=i;

         sort(id+,id+n+,cmp);

         int s=,t=n;

         for(int j=;j<=l;j++) {

             while(s<=n&&flag[i][id[s]])

               s++;

             while(t&&!flag[i][id[t]])

               t--;

             if(s>=t)

               break;

             flag[i][id[s]]=;

             flag[i][id[t]]=;

         }

         for(int j=;j<=n;j++)

           if(flag[i][j]&&!maxl[j][i]) {

             printf("-1");

             return ;

           }

     }

     for(int i=;i<=m;i++,printf("\n"))

       for(int j=;j<=n;j++)

         if(flag[i][j])

          printf("%d ",j);

     return ;

 }