考试辅导：程序员数据结构笔记（六）

 

七、围棋中的提子
　　在围棋比赛中，某一方（假设为黑方）在棋盘的某个位置（i，j）下子后，有可能提取对方（白方的一串子）。以W[19][19]表示一个棋盘，若W [i][j]=0表示在位置（i，j）上没有子，W[i][j]=1表示该位置上的是黑子，W[i][j]=-1表示该位置上是白子。可以用回溯法实现提子算法。
下列程序是黑棋（tag=1）下在（i，j）位置后判断是否可以吃掉某些白子，这些确定可以提掉的白子以一个线性表表示。
　　问题相应的数据结构有：
　　#define length 19 /*棋盘大小*/
　　#define max_num 361 /*棋盘中点的数量*/
　　struct position { int row; int col;
　　}; /*棋子位置*/
　　struct killed { struct position data[max_num]; int num;
　　} *p; /*存储可以吃掉的棋子位置*/
　　struct stack { struct position node[max_num]; int top;
　　}; /*栈*/
　　int w[length][length]; /*棋盘中双方的棋子分布*/
　　int visited[length][length]; /*给已搜索到的棋子位置作标记，初值为0，搜索到后为1*/

　　struct killed *kill(int w[length][length],int r,int c,int tag)
　　{ struct killed *p;
　　　struct position *s;
　　　struct stack S;
　　　for (i=0;i<length;i++)
　　　for (j=0;j<length;j++)
　　　　（1） ;
　　　S.top=-1; p->num=-1;
　　　if (w[r-1][c]==tag*(-1)) s->row=r-1; s->col=c;
　　　else if (w[r+1][c]==tag*(-1)) s->row=r+1; s->col=c;
　　　else if (w[r][c-1]==tag*(-1)) s->row=r; s->col=c-1;
　　　else if (w[r][c+1]==tag*(-1)) s->row=r; s->col=c+1;
　　　else p->len=0; return p;
　　　push(S,s); visited[s->row][s->col]=1;
　　　flag=search(s,tag);
　　　while ( （2）)
　　　{ push(S,s); visited[s->row][s->col]=1;
　　　　（3）;
　　　}
　　　while (S->top>=0)
　　　　{ pop(S);
　　　　　（4）;
　　　　　flag=search(s,tag);
　　　　　while (flag)
　　　　　{ push(S,s);
　　　　　　visit(s);
　　　　　　flag=search(s);
　　　　　}
　　　　}
　　}

　　void push( struct stack *S, struct position *s)
　　{ S->top++;
　　　S->node[S->top].row=s->row;
　　　S->node[S->top].col=s->col;
　　　p->num++;
　　　p->data[p->num].row=s->row;
　　　p->data[p->num].col=s->col;
　　}

　　void pop(struct stack *S)
　　{ S->top--;
　　}

　　struct position *gettop(struct stack *S)
　　{ struct position *s;
　　　s->row=S->data[S->top].row;
　　　s->row=S->data[S->top].row;
　　　return s;
　　}

上一页  [1] [2] [3] [4] 下一页  

上一篇文章： 考试辅导：程序员数据结构笔记（五）

下一篇文章： 没有了

　　　　　　　　　　　　　　　　　　　　　　　　　　　【发表评论】【加入收藏】【告诉好友】【打印此文】【关闭窗口】