The Alliances
In a fantasy world, there is a large island of a rectangular shape.
The sides of the island happen to be exactly R miles and C miles
long, and the whole island is divided into a grid of 
areas.
Some of the areas are uninhabited, and the rest are
occupied by villages of fantasy beings: elves, humans, dwarves, and hobbits.
Each area contains at most one village.
Two villages are considered neighbours if their areas share a side.
Recently, the villages became terrified of the Great Evil. In order to feel safer,
each village has decided to form military alliances with some of its neighbours.
An alliance always involves two neighbouring villages, and it is
a mutual and symmetric agreement.
Depending on the species living in the village, the inhabitants
will not feel safe unless a specific configuration of alliances is formed:
- The elves feel confident, and therefore need exactly one alliance.
- Human villages require alliances with exactly two neighbours.
Moreover, leaving two opposite sides of the village exposed is bad for
tactical reasons. Therefore the two allied neighbours cannot be located
on opposite sides of the village.
- Dwarves require alliances with exactly three neighbours.
- Hobbits are extremely scared, and therefore need to have alliances with all four of their neighbours.
In other words, except for humans each village requires a particular number of alliances,
but does not care which neighbours will be its allies.
For humans there is an additional restriction: the allied neighbours
must not be on opposite sides of the village.
The conditions must be fulfilled irrespective of the position of the village on the map.
For example, a dwarf village desires three alliances. If it is located on the coast,
this means that it must have alliances with all three neighbours. If there is a
dwarf village in a corner of the island, its inhabitants will never feel safe.
Task specification
For a given island description, your task is to decide
whether it is possible to form alliances so that all inhabitants
of the island will feel safe. In case of a positive answer, your
task is also to suggest one viable configuration of alliances.
In case of multiple solutions, choose an arbitrary one.
Input specification
The first line of the input contains two integers R and C specifying
the size of the island. The following R lines encode a description of the island. Each line consists of C space-separated numbers between 0 and 4:
- 0 means uninhabited area,
- 1 means an elf village,
- 2 means a human village,
- 3 means a dwarf village.
- 4 means a hobbit village,
(Note that the number in the input always corresponds to the number of desired alliances for that village.)
Constraints
In all test cases assume that 
.
In test cases worth a total of 55 points we have 
. Out of these, in test cases worth 15 points 
.
Another batch of test cases worth 10 points contains maps with
only uninhabited areas and human villages. (This batch is not included
in the test cases worth 55 points.)
Output specification
If there is no solution, output a single line with the
string "Impossible!" (quotes for clarity).
Otherwise, output one valid map of alliances in the following format.
Each area should appear in the output as a matrix of 
characters.
If the area is uninhabited, the corresponding section of the output will be filled
with . (dot) symbols. If the area has a village there should be a
a symbol O (uppercase letter O) in the middle representing the village itself,
and there should be symbols X (uppercase letter X) representing a configuration of
its allies. The rest of the matrix should be filled with
. (dot) symbols.
For each village type, all possible layouts of alliances are shown in the image below.
Examples
input:
3 4
2 3 2 0
3 4 3 0
2 3 3 1
output:
............
.OXXOXXO....
.X..X..X....
.X..X..X....
.OXXOXXO....
.X..X..X....
.X..X..X....
.OXXOXXOXXO.
............
input:
1 2
2 1
output:
Impossible!
这是 CEOI2010 当场唯一会做的。。。
题目大意是：告诉一个70*70的格子里面每个点的度，每个格子只能往四周的四个格子连边，边是双向的，对于度为2的点所连的两条边不能在一条直线上，求出一组方案。
============================
如果没有对度为2的点连边的限制的话，就把格子黑白染色，建二分图，相邻的点连容量为1的边，黑点连源，白点连汇，容量都为要求的度。流之即可。
加上对度为2的点连边的限制，这样的方法出现的问题在于没法处理这个问题了。
但我们发现，对于度为2的点的限制可以化为：横向或者纵向都有且只有一条边，于是把度为2的点拆成横的和竖的两个点就行了。
/*
* $File: alliances.cpp
* $Date: Thu Jul 15 11:18:14 2010 +0800
* $Prob: CEOI 2010 The Alliances
* $Author: Tim
* $Addr: http://riesky.sk/ceoi2010/problem.php?contest=CEOI%202010%20Day%201&problem=alliances
*/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#define MAXL 71
#define MAXN (MAXL * MAXL * 2 + 10)
#define MAXM (MAXN * 4 + MAXN + MAXN) * 2
#define INFINITE 0x3f3f3f3f
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define OP(x) ((((x) - 1) ^ 1) + 1)
#define OP_DIR(x) ((x + 2) & 3)
using namespace std;
const int fx[] = {0, 1, 0, -1};
const int fy[] = {1, 0, -1, 0};
const int UP = 3,
DOWN = 1,
LEFT = 2,
RIGHT = 0;
int map[MAXL + 1][MAXL + 1];
int n, m;
void Init()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++)
for (int j = 0; j < m; j ++)
scanf("%d", &map[i][j]);
}
int N = 2, S = 0, T = 1;
int id[MAXL + 1][MAXL + 1][2];
int ID(int x, int y, int flag)
{
if (id[x][y][flag])
return id[x][y][flag];
return id[x][y][flag] = N ++;
}
int edge_id[MAXL + 1][MAXL + 1][4];
int Count = 0;
int begin[MAXN + 1], end[MAXM + 1], next[MAXM + 1], c[MAXM + 1];
void AddEdge(int a, int b, int f)
{
Count ++;
next[Count] = begin[a];
begin[a] = Count;
end[Count] = b;
c[Count] = f;
Count ++;
next[Count] = begin[b];
begin[b] = Count;
end[Count] = a;
c[Count] = 0;
}
int tot_flow[2];
void BuildGraph()
{
for (int i = 0; i < n; i ++)
for (int j = 0; j < m; j ++)
if (map[i][j])
{
if ((i + j) & 1)
{
for (int k = 0; k < 4; k ++)
{
int x = i + fx[k], y = j + fy[k];
if (x >= 0 && x < n && y >= 0 && y < m && map[x][y])
{
AddEdge(ID(i, j, (map[i][j] == 2 ? (k & 1) : 0)),
ID(x, y, (map[x][y] == 2 ? (k & 1) : 0)),
1);
edge_id[i][j][k] = edge_id[x][y][OP_DIR(k)] = Count;
}
}
if (map[i][j] == 2)
{
AddEdge(S, ID(i, j, 0), 1);
AddEdge(S, ID(i, j, 1), 1);
}
else
AddEdge(S, ID(i, j, 0), map[i][j]);
}
else
{
if (map[i][j] == 2)
{
AddEdge(ID(i, j, 0), T, 1);
AddEdge(ID(i, j, 1), T, 1);
}
else
AddEdge(ID(i, j, 0), T, map[i][j]);
}
tot_flow[(i + j) & 1] += map[i][j];
}
}
int cur[MAXN + 1], d[MAXN + 1], pre[MAXN + 1], a[MAXN + 1], cnt[MAXN + 1];
int sap()
{
int flow = 0, now, tmp, u;
a[u = S] = INFINITE;
cnt[0] = N;
memcpy(cur, begin, sizeof(begin[0]) * N);
while (d[S] < N)
{
for (now = cur[u]; now; now = next[now])
if (c[now] && d[u] == d[end[now]] + 1)
break;
if (now)
{
tmp = end[now];
pre[tmp] = cur[u] = now;
a[tmp] = MIN(a[u], c[now]);
if ((u = tmp) == T)
{
flow += (tmp = a[T]);
do
{
c[pre[u]] -= tmp;
c[OP(pre[u])] += tmp;
u = end[OP(pre[u])];
}
while (u != S);
a[S] = INFINITE;
}
}
else
{
if ((--cnt[d[u]]) == 0)
break;
cur[u] = begin[u], d[u] = N;
for (now = begin[u]; now; now = next[now])
if (c[now] && d[u] > d[end[now]] + 1)
d[u] = d[end[now]] + 1, cur[u] = now;
cnt[d[u]] ++;
if (u != S)
u = end[OP(pre[u])];
}
}
return flow;
}
bool ans;
void Solve()
{
BuildGraph();
ans = true;
if (tot_flow[0] != tot_flow[1])
ans = false;
else if (sap() != tot_flow[0])
ans = false;
}
void Print()
{
if (!ans)
puts("Impossible!");
else
{
for (int i = 0; i < n; i ++)
{
for (int j = 0; j < m; j ++)
{
printf("%c", '.');
printf("%c", c[edge_id[i][j][UP]] ? 'X' : '.');
printf("%c", '.');
}
printf("\n");
for (int j = 0; j < m; j ++)
{
printf("%c", c[edge_id[i][j][LEFT]] ? 'X' : '.');
printf("%c", map[i][j] ? 'O' : '.');
printf("%c", c[edge_id[i][j][RIGHT]] ? 'X' : '.');
}
printf("\n");
for (int j = 0; j < m; j ++)
{
printf("%c", '.');
printf("%c", c[edge_id[i][j][DOWN]] ? 'X' : '.');
printf("%c", '.');
}
printf("\n");
}
}
}
int main()
{
freopen("alliances.in", "r", stdin);
freopen("alliances.out", "w", stdout);
Init();
Solve();
Print();
return 0;
}