![这个最佳答案由 额外减小 给出,感谢 额外减小 的回答。
单击隐藏图章](source/plugin/study_bestanswer/images/bestAnswer.gif) 诶嘿嘿,硬是用STL(没用任何算法)搞出来了#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
//膜拜[url=home.php?mod=space&uid=1292144]@zhangjinxuan[/url] dalao %%%orz
//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
//我这个蒟蒻被zhangjinxuan,mushezi,yuanhao,sfqxx薄纱啦!!!
//FCOI please do not ak me!!!
//谢谢zhangjinxuan大佬提供特殊约定~
typedef struct{
int row;
int count;
}hh; //统计各行的0的数目
inline bool cmp(hh a,hh b)
{
return a.count<b.count;
}
inline void out_row(bool *sz,int col_max)
{
for(int i=0;i<col_max;i++)
{
printf("%d.",sz[i]);
}
}
int main()
{
set<int>rows;
int n,m,cnt,ch,stepcnt=0;
hh rs[2010];
bool sz[2010][2010];
scanf("%d%d",&n,&m);
getchar();
for(int i=0;i<n;i++)//hang
{
cnt=0;
for(int j=0;j<m;j++)//lie
{
ch=getchar();
//printf("%d.",ch);
if(ch=='0')
{
sz[i][j]=false;
}
else
{
sz[i][j]=true;
cnt++;
}
getchar();
}
getchar();
rs[i].count=cnt;
rs[i].row=i;
stepcnt+=m-cnt;
}
sort(rs,rs+n,cmp);
/*for(int k=0;k<n;k++)
{
out_row(sz[rs[k].row],m);
putchar('\n');
}*/
stepcnt+=n;
for(int i=0;i<n;i++)
{
int r=rs[i].row;
for(int j=0;j<m;j++)
{
if(!sz[r][j])
{
if(rows.count(j)==0 and i!=0)
{
printf("-1\n");
return 0;
}
if(i==0)rows.insert(j);
}
}
}
printf("%d\n",stepcnt);
for(int i=0;i<n;i++)
{
int r=rs[i].row;
printf("1 %d\n",r+1);
for(int j=0;j<m;j++)
{
if(!sz[r][j])
{
printf("2 %d\n",j+1);
}
}
}
}
一个排序,排出每行的'0'的个数
然后用set看是否真包含。 |