当前位置:编程学习 > C/C++ >>

队列-----链式存储结构及其操作算法的实现-----HOJ2581

[cpp]  
#ifndef _QUEUE_LINK_H_HUMING_INCLUDE_  
#define _QUEUE_LINK_H_HUMING_INCLUDE_  
#include<cstdio>  
template <class T>  
class  node  
{  
    public:  
    T data;  
    node<T>* next;  
    node():next(NULL) {}; //No-arg constructor  
    node(T p)//Constructor  
    {  
        this->data=p;//"this" means "class node"  
        next=NULL;  
    };  
};  
//node defination  
template <class T>  
class queue  
{  
public:  
    queue();  
    ~queue();// to avoid memory leak, a destructor is needed.  
    bool empty();  
    void pop();  
    void push(T x);  
    T front();  
private:  
    node<T> *head,*tail;  
};  
template <class T>  
void queue<T>::push(T x)  
{  
    node<T> *q=new node<T>;  
    q->data=x;  
    q->next=NULL;  
    tail->next=q;  
    tail=q;  
}  
template <class T>  
queue<T>::queue()  
{  
    head=new node<T>;  
    head->next=NULL;  
    tail=head;  
}  
template <class T>  
bool queue<T>::empty()  
{  
    return (tail==head);//这个写法简单!  
}  
template <class T>  
void queue<T>::pop()  
{  
    if(!empty())  
    {  
        node<T>* x;  
        x=head->next;  
        head->next=x->next;  
        if(x->next==NULL) tail=head;  
        delete x;  
    }  
}  
template <class T>  
T queue<T>::front()  
{  
    return (head->next->data);  
}//不用判断空,调用之前写一下判断一下就行  
template <class T>  
queue<T>::~queue()//delete all nodes including "head".  
{  
    node<T>* x;  
    while(head)  
    {  
            x=head;  
            head=head->next;  
            delete x;  
    }  
}  
#endif  
[cpp] view plaincopy
#include<iostream>  
#include  "queue_link.h"  
#include<cstring>  
#define maxlen 22  
#include<cstdio>  
int mat[maxlen][maxlen],black,white;  
int dir[4][2]= {{-1,0},{1,0},{0,-1},{0,1}};  
using namespace std;  
struct ND  
{  
    int x,y;  
};  
void BFS(ND s,int n)  
{  
    int f1=0,f2=0,count=0;  
    queue<ND> q;  
    ND  ol,ne;  
    while(!q.empty())  
    {  
        q.pop();  
    }  
    q.push(s);  
    mat[s.x][s.y]=3;  
    while(!q.empty())  
    {  
        ol=q.front();  
        q.pop();  
        count++;  
        //出队之后count再更新,入队不更新  
        for(int i=0; i<4; i++)  
        {  
            ne.x=ol.x+dir[i][0];  
            ne.y=ol.y+dir[i][1];  
            if(ne.x>=1&&ne.x<=n&&ne.y>=1&&ne.y<=n)  
            {  
                if(mat[ne.x][ne.y]==0)  
                {  
                    mat[ne.x][ne.y]=3;  
                          q.push(ne);  
                }  
                else if(mat[ne.x][ne.y]==1)  
                    f1=1;  
                else if(mat[ne.x][ne.y]==2)  
                    f2=1;  
            }  
        }  
    }  
    if(f1+f2!=2)//只要遇到两个都有这种情况,那么就说明这种情况是黑白棋包围  
    {  
        if(f2)  
            black+=count;  
        if(f1)  
            white+=count;  
    }  
}  
int main()  
{  
    int n,b,w,i,j;  
    ND s;  
    while(cin >> n&& n)  
    {  
        black=0,white=0;  
        memset(mat,0,sizeof(mat));  
        cin >> b >> w;  
        while(b--)  
        {  
            cin >> i >> j;  
            mat[i][j]=2;//b  
        }  
        while(w--)  
        {  
            cin >> i >> j;  
            mat[i][j]=1;//w  
        }  
        for(i=1; i<=n; i++)
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,