In the process of preparation to Halloween it was decided to plant some
pumpkins on
the n × m meters
rectangular platform. The platform is divided
to n × midentical
square cells with 1 meter length sides.
The arrangement of
pumpkins was carefully prepared, and you are given the resulting plan. For each
cell of this platform it is given how many pumpkins should be planted in it. All
these quantities appear to be from 1 to 5,
inclusive.
Special pumpkin-landing machine was bought
to plant Halloween symbols. It can perform a simple operation: plant pumpkin to
the cell, specified by its coordinates (the first coordinate ranges 1
to n, and the second one ranges 1
to m).
At the last moment
an unpleasant feature of the machine was discovered. Every time this machine
plants a pumpkin to the specified cell, one more pumpkin is also planted to all
cells, which are adjacent to the specified one and already have at least one
pumpkin in it. One cell is called adjacent to another one if they share a
side.
Besides for technical reasons you cannot specify the
same cell twice.
Now Halloween celebration is under the
threat of failure. You are asked to write the program which finds the sequence
of n × m operations
leading to demanded landing of pumpkins, or informs that it is
impossible.
The first line of input contains two
integers n and m —
sizes of the field (1
≤ n,m ≤ 200).
Next n lines
contain m integers from 1 to 5 — how many
pumpkins should be planted in each cell of the platform. Numbers in lines are
separated by single spaces.
If the solution exists,
print n × m lines
with two numbers in each: a line and a column numbers, where the next pumpkin
should be landed. If there are multiple solutions, print any of
them.
If the solution does not exist, print a single line
"No solution" (quotes for clarity).
sample input |
sample output |
1 2 1 2 |
1 2 1 1 |
sample input |
sample output |
1 3 1 3 1 |
1 2 1 3 1 1 |
sample input |
sample output |
3 3 2 4 2 2 1 2 3 2 3 |
1 2 3 1 3 3 1 1 1 3 3 2 2 1 2 3 2 2 |
sample input |
sample output |
2 1 1 1 |
No solution
|
|
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 |
#include<queue>#include<stack>#include<iostream>#include<cstdlib>using
namespace std;const
int maxn=200+10;const
int di[]={-1,0,1,0},dj[]={0,1,0,-1};int map[maxn][maxn],n,m;bool
mark[maxn][maxn]={0};struct
node{int
x,y;node(int
x,int y):x(x),y(y){}void
show(){cout<<x<<" "<<y<<endl;}};void
Cant(){cout<<"No solution"<<endl;exit(0);}int
main(){cin>>n>>m; queue<node> Q;stack<node> S;for(int
i = 0; i <= n+1;i++) for(int
j = 0; j<=m+1;j++) map[i][j]=10;for(int
i = 1; i<=n;i++)REP(int
j =1; j<=m;j++){cin>>map[i][j]; if(map[i][j]==1)Q.push(node(i,j));}while(Q.size()){node cur=Q.front();Q.pop();S.push(cur);mark[cur.x][cur.y]=true; for(int
k =0; k <=3;k++){int
t=di[k]+cur.x,u=dj[k]+cur.y;if(!mark[t][u]&&map[t][u]!=10){map[t][u]–;if(!map[t][u])Cant();if(map[t][u]==1)Q.push(node(t,u));}}}if(S.size()!=n*m)Cant();while(S.size()){S.top().show();S.pop();}} |
原文：http://www.cnblogs.com/LyningCoder/p/3662955.html