1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
| #include <cstdio>
#include <vector>
using namespace std;
const int N = 5510;
struct Node
{
int x, y;
int l, r, u, d;
};
vector<Node> p;
int top, ans[N];
int n, m, s[N];
void init()
{
p.push_back({0, 0, m, 1, 0, 0});
for (int i = 1; i < m; i++)
p.push_back({0, i, i - 1, i + 1, i, i});
p.push_back({0, m, m - 1, 0, m, m});
}
void add(int &hd, int &tl, int x, int y)
{
int t = p.size();
p.push_back({x, y, hd, tl, y, p[y].d});
tl = p[hd].r = p[tl].l = p[y].d = p[p[y].d].u = t;
s[y]++;
}
void remove(int x)
{
p[p[x].l].r = p[x].r, p[p[x].r].l = p[x].l;
for (int i = p[x].d; i != x; i = p[i].d)
for (int j = p[i].r; j != i; j = p[j].r)
{
s[p[j].y]--;
p[p[j].d].u = p[j].u, p[p[j].u].d = p[j].d;
}
}
void resume(int x)
{
for (int i = p[x].u; i != x; i = p[i].u)
for (int j = p[i].l; j != i; j = p[j].l)
{
s[p[j].y]++;
p[p[j].d].u = j, p[p[j].u].d = j;
}
p[p[x].l].r = x, p[p[x].r].l = x;
}
bool dfs()
{
if (!p[0].r)
return true;
int t = p[0].r;
for (int i = p[0].r; i; i = p[i].r)
if (s[i] <= s[t])
t = i;
if (!t)
return false;
remove(t);
for (int i = p[t].d; i != t; i = p[i].d)
{
ans[++top] = p[i].x;
for (int j = p[i].r; j != i; j = p[j].r)
remove(p[j].y);
if (dfs())
return true;
for (int j = p[i].l; j != i; j = p[j].l)
resume(p[j].y);
top--;
}
resume(t);
return false;
}
int main()
{
scanf("%d%d", &n, &m);
init();
for (int i = 1, a; i <= n; i++)
{
int hd = p.size(), tl = p.size();
for (int j = 1; j <= m; j++)
{
scanf("%d", &a);
if (a)
add(hd, tl, i, j);
}
}
if (dfs())
for (int i = 1; i <= top; i++)
printf("%d ", ans[i]);
else
puts("No Solution!");
return 0;
}
|