Sicilly 1152馬の簡単周遊問題(5*6)
Description
5 * 6 , 29 , , , , 。
, , , :
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
“ ” , 15 , 2、4、7、11、19、23、26 28。 , 1 9 14。
Input
。 N(1<=N<=30), 。 -1 , 。
Output
, 。 , 30 , 。 。
:
1 :
Node ,
x //
y //
z //
s //
bool array[m][n]
stack list , 。
2 :
1)push begin into list
2)while list is not empty
do
find one node of the next can search;
if(find),push it into list;
else not find, pop the top of the list.
end while
3) if(the size of list == 5*6), print the result
else print the error message.
end.
#include
#include
#include
#define m 5
#define n 6
using namespace std;
struct Node {
int z; // the number of the node
int x; // the x-coordinate
int y; // the y-coordinate
int s; // the number of the next node had search
Node(){
z = 0;
x = 0;
y = 0;
s = 0;
}
Node(int zz) {
z = zz;
x = (z - 1) / 6;
y = z - 6 * x - 1;
s = 0;
}
Node(int xx, int yy) {
x = xx;
y = yy;
z = 6 * x + y + 1;
s = 0;
}
Node findNext(int i) {
int xx;
int yy;
switch(i) {
case 1: xx = x - 2; yy = y - 1; break;
case 2: xx = x - 2; yy = y + 1; break;
case 3: xx = x - 1; yy = y + 2; break;
case 4: xx = x + 1; yy = y + 2; break;
case 5: xx = x + 2; yy = y + 1; break;
case 6: xx = x + 2; yy = y - 1; break;
case 7: xx = x + 1; yy = y - 2; break;
case 8: xx = x - 1; yy = y - 2; break;
default: xx = 0; yy = 0; break;
}
Node node(xx, yy);
return node;
}
bool isValid() {
return x >= 0 && x < m && y >= 0 && y < n;
}
};
int main() {
int N;
while (cin >> N && N != -1) {
Node begin(N);
//the list stored the node had search
stack list;
//the array to marck the nodes whether had been search
bool arr[m][n];
memset(arr, false, m*n);
list.push(begin);
arr[begin.x][begin.y] = true;
//the algorithm of DSF
while (!list.empty()) {
cout << list.size() << endl;
if (list.size() == m*n) {
break;
}
//the num of the node had search
int i;
for (i = list.top().s+1; i <= 8; i++) {
Node item = list.top().findNext(i);
list.top().s = i;
//if the next node haven't searched, push into the list
if (item.isValid() && !arr[item.x][item.y]) {
list.push(item);
arr[item.x][item.y] = true;
break;
}
}
//if do not find the node, pop the top of the list
if (i > 8) {
arr[list.top().x][list.top().y] = false;
list.pop();
}
}
//succeed
if (list.size() == 30) {
stack ll;
for (int i = 0; i < 30; i++) {
ll.push(list.top());
list.pop();
}
for (int i = 0; i < 30; i++) {
cout << ll.top().z << " ";
ll.pop();
}
cout << endl;
}
else {
cout << "Not Find!" << endl;
}
}
return 0;
}