队列-----链式存储结构及其操作算法的实现-----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++ ,