![]() |
#2
独立观察员2012-10-25 22:34
|

#include<stdio.h>
#include <stdlib.h>
#define STACK_INIT_SIZE 70
#define STACK_SIZE 10
#define ERROR 0
#define OK 1
#define OVERFLOW -2
typedef int Status;
typedef int ElemType;
typedef struct{
int i;
int j;
ElemType a;
}PassStackElem;
typedef struct{
PassStackElem * top;
PassStackElem * base;
int size;
}PassStack;
bool InitStack(PassStack &S) {
// 初始化栈
S.base = (PassStackElem *)malloc(STACK_INIT_SIZE*sizeof(PassStackElem));
if(!S.base)
exit(0);
S.top = S.base;
S.size = 0;
return true;
} // InitStack
bool pop(PassStack &S, ElemType &e, int &m, int &n) {
if(S.top == S.base)
return false;
e = --S.top->a;
m = S.top->i;
n = S.top->j;
S.size--;
return true;
}
bool push(PassStack &S, int v, int m, int n) {
if(S.top - S.base >= S.size)
{
S.base = (PassStackElem *)realloc(S.base, (S.size + STACK_SIZE)*sizeof(PassStackElem));
if(!S.base)
exit(0);
S.top = S.base + S.size;
S.size += STACK_SIZE;
}
S.top->i = m;
S.top->j = n;
S.top->a = v;
S.top++;
S.size++;
return true;
} // Push
Status StackEmpty(PassStack &S)
{
if(S.top==S.base)
return 1;
else return 0;
} //判断空栈
Status find(PassStack s, int m, int n){
PassStackElem * p = s.top-1;
int i=1;
while(i <= s.size){
if(p->i == m && p->j == n)
break;
p--;
i++;
}
if(i <= s.size)
return 1;
else
return 0;
}
void print(PassStack ps, int *board){
int m,n,a,i=1;
while(!StackEmpty(ps)){
pop(ps, a, m, n);
board[8*m+n] = i;
printf("%d ",board[8*m+n]);
//board[m][n] = i;
i++;
}
for(i=0; i<8; i++){
for(int j=0; j<8; j++)
printf("%d ",board[8*i+j]);
printf("\n");
}
}
void explore(ElemType *board,PassStack &ps, int i, int j){
int m = i;
int n = j;
int val;
push(ps, 0, m, n);
while(ps.size <= 64){
if(board[8*m+n] == 0){
board[8*m+n]++;
if(i-2>=0 && j+1<=7){
m = i - 2;
n = j + 1;
if(find(ps,m,n)){
m = i;
n = j; //栈中已存在,恢复下标;
}
else{ //栈中不存在,入栈;
board[8*m+n] = 0;
val = board[8*m+n];
push(ps,val,m,n);
i = m;
j = n;
}
}
}
if(board[8*m+n] == 1){
board[8*m+n]++;
if(i-1>=0 && j+2<=7){
m = i - 1;
n = j + 2;
if(find(ps,m,n)){
m = i;
n = j; //栈中已存在,恢复下标;
}
else{ //栈中不存在,入栈;
board[8*m+n] = 0;
val = board[8*m+n];
push(ps,val,m,n);
i = m;
j = n;
}
}
}
if(board[8*m+n] == 2){
board[8*m+n]++;
if(i+1<=7 && j+2<=7){
m = i + 1;
n = j + 2;
if(find(ps,m,n)){
m = i;
n = j; //栈中已存在,恢复下标;
}
else{ //栈中不存在,入栈;
board[8*m+n] = 0;
val = board[8*m+n];
push(ps,val,m,n);
i = m;
j = n;
}
}
}
if(board[8*m+n] == 3){
(board[8*m+n])++;
if(i+2<=7 && j+1<=7){
m = i + 2;
n = j + 1;
if(find(ps,m,n)){
m = i;
n = j; //栈中已存在,恢复下标;
}
else{ //栈中不存在,入栈;
board[8*m+n] = 0;
val = board[8*m+n];
push(ps,val,m,n);
i = m;
j = n;
}
}
}
if(board[8*m+n] == 4){
(board[8*m+n])++;
if(i+2<=7 && j-1>=0){
m = i + 2;
n = j - 1;
if(find(ps,m,n)){
m = i;
n = j; //栈中已存在,恢复下标;
}
else{ //栈中不存在,入栈;
board[8*m+n] = 0;
val = board[8*m+n];
push(ps,val,m,n);
i = m;
j = n;
}
}
}
if(board[8*m+n] == 5){
(board[8*m+n])++;
if(i+1<=7 && j-2>=0){
m = i + 1;
n = j - 2;
if(find(ps,m,n)){
m = i;
n = j; //栈中已存在,恢复下标;
}
else{ //栈中不存在,入栈;
board[8*m+n] = 0;
val = board[8*m+n];
push(ps,val,m,n);
i = m;
j = n;
}
}
}
if(board[8*m+n] == 6){
(board[8*m+n])++;
if(i-1>=0 && j-2>=0){
m = i - 1;
n = j - 2;
if(find(ps,m,n)){
m = i;
n = j; //栈中已存在,恢复下标;
}
else{ //栈中不存在,入栈;
board[8*m+n] = 0;
val = board[8*m+n];
push(ps,val,m,n);
i = m;
j = n;
}
}
}
if(board[8*m+n] == 7){
(board[8*m+n])++;
if(i-2>=0 && j-1>=0){
m = i - 2;
n = j - 1;
if(find(ps,m,n)){
m = i;
n = j; //栈中已存在,恢复下标;
}
else{ //栈中不存在,入栈;
board[8*m+n] = 0;
val = board[8*m+n];
push(ps,val,m,n);
i = m;
j = n;
}
}
}
if(board[8*m+n] == 8){
if(ps.size == 64){
break;
}
else {
pop(ps,val,m,n);
}
}
}
}
int main(){
PassStack ps;
int i,j;
int board[64] = {};
InitStack(ps);
printf("请输入初始位置i和j:(两个不大于7的正整数,包括0)\n");
scanf("%d%d",&i,&j);
explore(board, ps, i, j);
print(ps,board);
return 0;
}
#include <stdlib.h>
#define STACK_INIT_SIZE 70
#define STACK_SIZE 10
#define ERROR 0
#define OK 1
#define OVERFLOW -2
typedef int Status;
typedef int ElemType;
typedef struct{
int i;
int j;
ElemType a;
}PassStackElem;
typedef struct{
PassStackElem * top;
PassStackElem * base;
int size;
}PassStack;
bool InitStack(PassStack &S) {
// 初始化栈
S.base = (PassStackElem *)malloc(STACK_INIT_SIZE*sizeof(PassStackElem));
if(!S.base)
exit(0);
S.top = S.base;
S.size = 0;
return true;
} // InitStack
bool pop(PassStack &S, ElemType &e, int &m, int &n) {
if(S.top == S.base)
return false;
e = --S.top->a;
m = S.top->i;
n = S.top->j;
S.size--;
return true;
}
bool push(PassStack &S, int v, int m, int n) {
if(S.top - S.base >= S.size)
{
S.base = (PassStackElem *)realloc(S.base, (S.size + STACK_SIZE)*sizeof(PassStackElem));
if(!S.base)
exit(0);
S.top = S.base + S.size;
S.size += STACK_SIZE;
}
S.top->i = m;
S.top->j = n;
S.top->a = v;
S.top++;
S.size++;
return true;
} // Push
Status StackEmpty(PassStack &S)
{
if(S.top==S.base)
return 1;
else return 0;
} //判断空栈
Status find(PassStack s, int m, int n){
PassStackElem * p = s.top-1;
int i=1;
while(i <= s.size){
if(p->i == m && p->j == n)
break;
p--;
i++;
}
if(i <= s.size)
return 1;
else
return 0;
}
void print(PassStack ps, int *board){
int m,n,a,i=1;
while(!StackEmpty(ps)){
pop(ps, a, m, n);
board[8*m+n] = i;
printf("%d ",board[8*m+n]);
//board[m][n] = i;
i++;
}
for(i=0; i<8; i++){
for(int j=0; j<8; j++)
printf("%d ",board[8*i+j]);
printf("\n");
}
}
void explore(ElemType *board,PassStack &ps, int i, int j){
int m = i;
int n = j;
int val;
push(ps, 0, m, n);
while(ps.size <= 64){
if(board[8*m+n] == 0){
board[8*m+n]++;
if(i-2>=0 && j+1<=7){
m = i - 2;
n = j + 1;
if(find(ps,m,n)){
m = i;
n = j; //栈中已存在,恢复下标;
}
else{ //栈中不存在,入栈;
board[8*m+n] = 0;
val = board[8*m+n];
push(ps,val,m,n);
i = m;
j = n;
}
}
}
if(board[8*m+n] == 1){
board[8*m+n]++;
if(i-1>=0 && j+2<=7){
m = i - 1;
n = j + 2;
if(find(ps,m,n)){
m = i;
n = j; //栈中已存在,恢复下标;
}
else{ //栈中不存在,入栈;
board[8*m+n] = 0;
val = board[8*m+n];
push(ps,val,m,n);
i = m;
j = n;
}
}
}
if(board[8*m+n] == 2){
board[8*m+n]++;
if(i+1<=7 && j+2<=7){
m = i + 1;
n = j + 2;
if(find(ps,m,n)){
m = i;
n = j; //栈中已存在,恢复下标;
}
else{ //栈中不存在,入栈;
board[8*m+n] = 0;
val = board[8*m+n];
push(ps,val,m,n);
i = m;
j = n;
}
}
}
if(board[8*m+n] == 3){
(board[8*m+n])++;
if(i+2<=7 && j+1<=7){
m = i + 2;
n = j + 1;
if(find(ps,m,n)){
m = i;
n = j; //栈中已存在,恢复下标;
}
else{ //栈中不存在,入栈;
board[8*m+n] = 0;
val = board[8*m+n];
push(ps,val,m,n);
i = m;
j = n;
}
}
}
if(board[8*m+n] == 4){
(board[8*m+n])++;
if(i+2<=7 && j-1>=0){
m = i + 2;
n = j - 1;
if(find(ps,m,n)){
m = i;
n = j; //栈中已存在,恢复下标;
}
else{ //栈中不存在,入栈;
board[8*m+n] = 0;
val = board[8*m+n];
push(ps,val,m,n);
i = m;
j = n;
}
}
}
if(board[8*m+n] == 5){
(board[8*m+n])++;
if(i+1<=7 && j-2>=0){
m = i + 1;
n = j - 2;
if(find(ps,m,n)){
m = i;
n = j; //栈中已存在,恢复下标;
}
else{ //栈中不存在,入栈;
board[8*m+n] = 0;
val = board[8*m+n];
push(ps,val,m,n);
i = m;
j = n;
}
}
}
if(board[8*m+n] == 6){
(board[8*m+n])++;
if(i-1>=0 && j-2>=0){
m = i - 1;
n = j - 2;
if(find(ps,m,n)){
m = i;
n = j; //栈中已存在,恢复下标;
}
else{ //栈中不存在,入栈;
board[8*m+n] = 0;
val = board[8*m+n];
push(ps,val,m,n);
i = m;
j = n;
}
}
}
if(board[8*m+n] == 7){
(board[8*m+n])++;
if(i-2>=0 && j-1>=0){
m = i - 2;
n = j - 1;
if(find(ps,m,n)){
m = i;
n = j; //栈中已存在,恢复下标;
}
else{ //栈中不存在,入栈;
board[8*m+n] = 0;
val = board[8*m+n];
push(ps,val,m,n);
i = m;
j = n;
}
}
}
if(board[8*m+n] == 8){
if(ps.size == 64){
break;
}
else {
pop(ps,val,m,n);
}
}
}
}
int main(){
PassStack ps;
int i,j;
int board[64] = {};
InitStack(ps);
printf("请输入初始位置i和j:(两个不大于7的正整数,包括0)\n");
scanf("%d%d",&i,&j);
explore(board, ps, i, j);
print(ps,board);
return 0;
}