不知道别人会不会和我犯同样的错。
/*
ID: wangjun30
LANG: C++11
TASK:
*/
// Code by Wutiruo
//Optimizers
//#pragma GCC optimize(2,3,"Ofast","-fgcse","-fgcse-lm","-fipa-sra","-ftree-pre","-ftree-vrp","-fpeephole2","-ffast-math","-fsched-spec","unroll-loops","-falign-jumps","-falign-loops","-falign-labels","-fdevirtualize","-fcaller-saves","-fcrossjumping","-fthread-jumps","-funroll-loops","-freorder-blocks","-fschedule-insns","inline-functions","-ftree-tail-merge","-fschedule-insns2","-fstrict-aliasing","-falign-functions","-fcse-follow-jumps","-fsched-interblock","-fpartial-inlining","no-stack-protector","-freorder-functions","-findirect-inlining","-fhoist-adjacent-loads","-frerun-cse-after-loop","inline-small-functions","-finline-small-functions","-ftree-switch-conversion","-foptimize-sibling-calls","-fexpensive-optimizations","inline-functions-called-once","-fdelete-null-pointer-checks","inline","fast-math","unroll-loops")
//#pragma GCC target("sse3","sse2","sse","avx","sse4","sse4.1","sse4.2","ssse3","f16c")
//#pragma GCC diagnostic error "-fwhole-program","-fcse-skip-blocks","-funsafe-loop-optimizations","-std=c++14"
//Only the last two lines are available on luogu
//Main Code
#include<bits/stdc++.h>
using namespace std;
//#include<bits/extc++.h>
//using namespace __gnu_cxx;
//Note: this header can't be used in Dev-C++
#define ll long long
namespace FastIO_fread{
char buf[4194304],*p1=buf,*p2=buf,pbuf[4194304],*pp=pbuf;
inline char gc()
{
return p1==p2&&(p2=(p1=buf)+fread(buf,1,4194304,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
int x=0;
char ch=gc(),flag=0;
while(ch<'0'||ch>'9')
flag|=(ch=='-'),ch=gc();
while(ch>='0'&&ch<='9')
x=(x<<3)+(x<<1)+ch-'0',ch=gc();
return flag?~x+1:x;
}
inline void push(char c)
{
if(pp-pbuf==4194304)
fwrite(pbuf,1,4194304,stdout),pp=pbuf;
*pp++=c;
}
inline void write(int x)
{
static int sta[20];
int top=0;
if(x<0)
push('-'),x=-x;
do
sta[top++]=x%10,x/=10;
while(x);
while(top)
push(sta[--top]+'0');
}
void flush()
{
fwrite(pbuf,pp-pbuf,1,stdout);
}
}
//using namespace FastIO_fread;
int _LINE_R[1010];
#define assert_line(n) {_LINE_R[__LINE__]++;assert(_LINE_R[__LINE__]<=n);}
//(){}0[]
struct DLXNode{
int left,right,down,up;
int row,col;
}DLX[6010];
typedef DLXNode DLXN;
DLXN &head=DLX[0];
int ccnt[510];//colomn's elements cnt
int rows[510];//row's first element
int ans[510];//answer
int tot,n,m;
enum PlaceType{
_up=1,
_down=2,
_left=3,
_right=4
};
void add_node(const int &r,const int &c){
DLX[++tot].up=DLX[c].up;
DLX[tot].down=c;
DLX[DLX[tot].up].down=tot;
DLX[c].up=tot;
if(!rows[r]){
DLX[tot].left=tot;
DLX[tot].right=tot;
rows[r]=tot;
}
else{
DLX[tot].right=rows[r];
DLX[tot].left=DLX[rows[r]].left;
DLX[rows[r]].left=tot;
DLX[DLX[tot].left].right=tot;
}
ccnt[c]++;
DLX[tot].row=r;
DLX[tot].col=c;
}
namespace DLXPrintf{
char ch[510][510];
char Data[15][15];
void PrintDLXf(){
memset(ch,' ',sizeof ch);
memset(Data,0,sizeof Data);
string str;
cerr<<"DLX state formated input: (For debug)\n";
Data[0][0]='H';
for(int i=head.right;i;i=DLX[i].right){
Data[0][i]=i+48;
for(int j=DLX[i].down;j!=i;j=DLX[j].down)
Data[DLX[j].row][DLX[j].col]='T';
}
for(int i=1;i<=n+1;i++)
for(int j=0;j<4*(m+2)-1;j++)
ch[i*4-1][j]='-';
for(int i=2;i<=m+1;i++)
for(int j=0;j<4*(n+2)-1;j++)
if(ch[j][i*4-1]==' ')
ch[j][i*4-1]='|';
else
ch[j][i*4-1]='+';
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)
if(Data[i][j])
ch[(i+1)*4-1][(j+1)*4-1]=Data[i][j];
for(int i=1;i<=n+1;i++){
bool flag=true;
for(int j=0;j<4*(m+2)-1;j++)
if(isalpha(ch[i*4-1][j]) or isdigit(ch[i*4-1][j]))
flag=false;
if(flag){
for(int j=0;j<4*(m+2)-1;j++)
if(ch[i*4-1][j]=='-')
ch[i*4-1][j]=' ';
else if(ch[i*4-1][j]=='+')
ch[i*4-1][j]='|';
}
}
for(int i=1;i<=m+1;i++){
bool flag=true;
for(int j=0;j<4*(n+2)-1;j++)
if(isalpha(ch[j][i*4-1]) or isdigit(ch[j][i*4-1]))
flag=false;
if(flag){
for(int j=0;j<4*(n+2)-1;j++)
if(ch[j][i*4-1]=='|')
ch[j][i*4-1]=' ';
else if(ch[j][i*4-1]=='+')
ch[j][i*4-1]='-';
}
}
for(int i=1;i<(n+2)*4-1;i++){
ch[i][(m+2)*4]='\n';
ch[i][(m+2)*4+1]='\0';
cerr<<ch[i];
}
cerr<<'\n';
}
void PrintDLX(){
/*Reserved*/
}
}
using DLXPrintf::PrintDLXf;
using DLXPrintf::PrintDLX;
int _i,_j,_c,_k;
void Remove(int &c){
for(int i=DLX[c].down;i!=c;i=DLX[i].down)
for(int j=DLX[i].right;j!=i;j=DLX[j].right){
DLX[DLX[j].up].down=DLX[j].down;
DLX[DLX[j].down].up=DLX[j].up;
ccnt[DLX[j].col]--;
}
DLX[DLX[c].left].right=DLX[c].right;
DLX[DLX[c].right].left=DLX[c].left;
}
void Resume(int &c){
DLX[DLX[c].left].right=c;
DLX[DLX[c].right].left=c;
for(int i=DLX[c].down;i!=c;i=DLX[i].down)
for(int j=DLX[i].right;j!=i;j=DLX[j].right){
DLX[DLX[j].up].down=j;
DLX[DLX[j].down].up=j;
ccnt[DLX[j].col]++;
}
}
void dance(int dep){
if(head.right==0){
for(int i=1;i<dep;i++)
cout<<ans[i]<<' ';
cout<<flush;
exit(0);
}
int col=head.right,cs;
for(int i=head.right;i;i=DLX[i].right)
if(ccnt[i]<ccnt[col])
col=i;
PrintDLX();
Remove(col);
PrintDLX();
cs=DLX[col].down;
if(cs==col)
return;
//这个地方挂了两个小时,直接return了没有resume col这一列,大红大紫,还不知道哪里错了
while(cs!=col){
ans[dep]=DLX[cs].row;
PrintDLX();
for(int j=DLX[cs].right;j!=cs;j=DLX[j].right)
Remove(DLX[j].col);
PrintDLX();
dance(dep+1);
for(int j=DLX[cs].right;j!=cs;j=DLX[j].right)
Resume(DLX[j].col);
cs=DLX[cs].down;
}
Resume(col);
}
void Init(){
tot=m;
head.right=1;
head.left=m;
for(int i=1;i<=m;i++){
DLX[i].left=i-1;
DLX[i].right=i+1;
DLX[i].up=i;
DLX[i].down=i;
DLX[i].col=i;
}
DLX[m].right=0;
}
void Input(){
{
for(int i=1,tmp;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>tmp;
if(tmp)
add_node(i,j);
}
}
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m;
Init();
Input();
dance(1);
cout<<"No Solution!"<<flush;
return 0;
}
/*
6 7
0 0 1 1 0 1 0
1 0 0 0 1 0 1
0 1 1 0 0 1 0
1 0 0 0 1 0 0
0 1 0 0 0 0 1
0 1 0 1 1 0 1
*/