1 /*
2 6. 矩阵中填数. 当给出 N*N 的矩阵，要求用程序填入下列形式的数：
3
4 ① 倒填，例如N=5 ② 蛇形填数 ③ 回转填数
5
6 ┌─┬─┬─┬─┬─┐ ┌─┬─┬─┬─┬─┐ ┌─┬─┬─┬─┬─┐
7 │25│24│23│22│21│ │ 1│ 3│ 4│10│11│ │ 1│16│15│14│13│
8 ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤
9 │20│19│18│17│16│ │ 2│ 5│ 9│12│19│ │ 2│17│24│23│12│
10 ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤
11 │15│14│13│12│11│ │ 6│ 8│13│18│20│ │ 3│18│25│22│11│
12 ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤
13 │10│ 9│ 8│ 7│ 6│ │ 7│14│17│21│24│ │ 4│19│20│21│10│
14 ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤
15 │ 5│ 4│ 3│ 2│ 1│ │15│16│22│23│25│ │ 5│ 6│ 7│ 8│ 9│
16 └─┴─┴─┴─┴─┘ └─┴─┴─┴─┴─┘ └─┴─┴─┴─┴─┘
17 */
18
19 #include <iostream>
20 //#include <c>
21
22 using namespace std;
23
24 void showTheMatrix(int matrix[][5]);
25 void showSeparateLine(int n);
26 void computeForMatrix2(int matrix[][5]);
27 void computeForMatrix3(int matrix[][5]);
28 void findNextPos(int & i, int & j, int & direction);
29 void findNextPosForMatrix3(int & i, int & j, int & direction);
30 void initMatrix(int matrix[][5]);
31 const int N = 5;
32 int matrix[N][N];
33 void main()
34 {
35 //cout << "input value for N:";
36 //cin >> N;
37
38 //int matrix = new int[N][N];
39 int temp = 0;
40 for (int i = 0; i < N; i++)
41 {
42 for (int j = 0; j < N; j++)
43 {
44 matrix[i][j] = N*N - temp++;
45 }
46 }
47 showSeparateLine(1);
48 showTheMatrix(matrix);
49 //temp = 0;
50
51 computeForMatrix2(matrix);
52 showSeparateLine(2);
53 showTheMatrix(matrix);
54
55 showSeparateLine(3);
56 computeForMatrix3(matrix);
57 showTheMatrix(matrix);
58
59 }
60
61 void showTheMatrix(int matrix[][5])
62 {
63 for (int i = 0; i < N; i++)
64 {
65 for (int j = 0; j < N; j++)
66 {
67 cout << "\t" << matrix[i][j] << " ";
68 }
69 cout << '\n';
70 }
71 }
72
73 void computeForMatrix2(int matrix[][5])
74 {
75 int i = 0, j = 0;
76 int direction = -1;
77 for (int k = 0; k < N*N; k++)
78 {
79 matrix[i][j] = k + 1;
80 findNextPos(i, j, direction);
81
82 }
83 }
84
85 void findNextPos(int & i, int & j, int & direction)
86 {
87 int i_temp = i;
88 int j_temp = j;
89 int dir_temp = direction;
90 if (dir_temp == 1)
91 {
92 i_temp = i - 1;
93 j_temp = j + 1;
94 } else if (dir_temp == -1)
95 {
96 i_temp = i + 1;
97 j_temp = j - 1;
98 }
99
100 if (i_temp > N - 1 || j_temp > N - 1 || i_temp < 0 || j_temp < 0)
101 {
102 if (dir_temp == -1)
103 {
104 if (i+1 < N)
105 {
106 i_temp = i + 1;
107 j_temp = j;
108 } else {
109 i_temp = i;
110 j_temp = j + 1;
111 }
112 dir_temp = 1;
113 } else if (dir_temp == 1)
114 {
115 if (j + 1 < N)
116 {
117 i_temp = i;
118 j_temp = j+1;
119 } else {
120 i_temp = i + 1;
121 j_temp = j;
122 }
123 dir_temp = -1;
124 }
125 }
126 i = i_temp;
127 j = j_temp;
128 direction = dir_temp;
129 }
130
131 void initMatrix(int matrix[][5])
132 {
133 for (int i = 0; i < N; i++)
134 {
135 for (int j = 0; j < N; j++)
136 {
137 matrix[i][j] = -1;
138 }
139 }
140 }
141
142 void computeForMatrix3(int matrix[][5])
143 {
144 initMatrix( matrix );
145 int i = 0, j = 0;
146 int direction = -1; // -1: vertical 1: horizental
147 for (int k = 0; k < N*N; k++)
148 {
149 matrix[i][j] = k + 1;
150 findNextPosForMatrix3(i, j, direction);
151 }
152 }
153
154 void findNextPosForMatrix3(int & i, int & j, int & direction)
155 {
156 int i_temp, j_temp, dir_temp;
157 i_temp = i;
158 j_temp = j;
159 int tried = 0;
160 loop:
161 dir_temp = direction;
162 if (direction < 0)
163 {
164 //--i_temp;
165 if (i_temp - 1 < 0) // up is invalid
166 {
167 if (i_temp + 1 < N)
168 {
169 if (matrix[i_temp+1][j_temp] < 0) // down is blank
170 {
171 i_temp++;
172 } else { //down is filled change direction
173 direction = 1;
174 }
175 } else {
176 direction = 1;
177 }
178 } else { // up is valid
179 if (matrix[i_temp-1][j_temp] < 0) // up is blank
180 {
181 i_temp--;
182 } else { // up is filled
183 if (i_temp + 1 < N) // down is valid
184 {
185 if (matrix[i_temp + 1][j_temp] < 0) // down is blank
186 {
187 i_temp++;
188 } else { // down is filled
189 direction = 1;
190 }
191 } else { // down is invalid
192 direction = 1;
193 }
194 }
195 }
196 } else { // left or right
197 if (j_temp - 1 < 0) // left is invalid
198 {
199 if (j_temp + 1 < N) // right is valid
200 {
201 if (matrix[i_temp][j_temp + 1] < 0) // right is blank
202 {
203 j_temp++;
204 } else { // right is filled
205 direction = -1;
206 }
207 } else { // right is invalid
208 direction = -1;
209 }
210 } else { // left is valid
211 if (matrix[i_temp][j_temp - 1] < 0) // left is blank
212 {
213 j_temp--;
214 } else { // left is filled
215 if (matrix[i_temp][j_temp + 1] < 0) // right is blank
216 {
217 j_temp++;
218 } else {
219 direction = -1;
220 }
221 }
222 }
223 }
224 if (dir_temp != direction)
225 {
226 if (tried++ < 1)
227 {
228 goto loop;
229 }
230 }
231 i = i_temp;
232 j = j_temp;
233 }
234 void showSeparateLine(int n)
235 {
236 cout << "---------------matrix " << n << "-----------------\n";
237 }