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 “ ” , 1524711192326 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;
}