| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 381 人关注过本帖
标题:马踏棋盘问题,请问我这样写错在哪里?
只看楼主 加入收藏
独立观察员
Rank: 1
等 级:新手上路
帖 子:10
专家分:0
注 册:2012-10-25
结帖率:0
收藏
 问题点数:0 回复次数:1 
马踏棋盘问题,请问我这样写错在哪里?
程序代码:
#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;
}
搜索更多相关主题的帖子: color 
2012-10-25 21:47
独立观察员
Rank: 1
等 级:新手上路
帖 子:10
专家分:0
注 册:2012-10-25
收藏
得分:0 
【马踏棋盘】
*问题描述:将马随机放在国际象棋的8X8棋盘Bo阿rd[0..7,0..7]的某个方格中,马按走棋规则进行移动。要求每个方格上只进入一次,走遍棋盘上全部64个方格。编制非递归程序,求出马的行走路线 ,并按求出的行走路线,将数字1,2,…,64依次填入8X8的方阵输出之。
*测试数据:由读者指定,可自行指定一个马的初始位置。
*实现提示:每次在多个可走位置中选择一个进行试探,其余未曾试探过的可走位置必须用适当结构妥善管理,以备试探失败时的“回溯”(悔棋)使用。并探讨每次选择位置的“最佳策略”,以减少回溯的次数。
2012-10-25 22:34
快速回复:马踏棋盘问题,请问我这样写错在哪里?
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.050603 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved