image.cpp

设计一个算法

#include <iostream.h>
#include <fstream.h>
ifstream in("input.txt");
ofstream out("output.txt");
class position;
template <class T>  class queue;
class position
{public:
	int row,col;};
template <class T>
class node{
	friend queue<T>;
	private:
		T data;
		node<T> *next;
};
template <class T>
class queue
{public:
queue(){front=rear=0;}
~queue();
bool empty() const
{return((front)?false:true);}
T first() const;
T last() const;
queue<T>&enqueue(const T&x);
queue<T>&dequeue(T&x);
private:
	node<T> *front;
	node<T> *rear;
};
template <class T>
queue<T>::~queue()
{node<T> *next;
while(front){
	next=front->next;
	delete front;
	front=next;
}
}
template <class T>
T queue<T>::first() const
{
	if(empty()) throw OutOfBounds();
	return front->data;
}
template <class T>
T queue<T>::last() const
{
	if(empty()) throw OutOfBounds();
	return rear->data;
}
template <class T>
queue<T>&queue<T>::enqueue(const T&x)
{node<T> *p=new node<T>;
p->data=x;
p->next=0;
if(front) rear->next=p;
else front=p;
rear=p;
return *this;
}
template <class T>
queue<T> &queue<T>::dequeue(T&x)
{
	x=front->data;
	node<T> *p=front;
	front=front->next;
	delete p;
	return *this;
}
int main()
{
	int m,i,j;
	int **p;
	in>>m;
	p=new int*[m+2];
	for(i=0;i<m+2;i++)
	{
		p[i]=new int[m+2];
	}	
	for(i=0;i<=m+1;i++)
	{
		p[i][0]=p[i][m+1]=2;
	}
	for(i=0;i<=m+1;i++)
	{
		p[0][i]=p[m+1][i]=2;
	}
	for(i=1;i<m+1;i++)
		for(j=1;j<m+1;j++)
		{
			in>>p[i][j];
		}
	position offset[4];
	position here,nbr;
	offset[0].row=0;offset[0].col=1;
	offset[1].row=1;offset[1].col=0;
	offset[2].row=0;offset[2].col=-1;
	offset[3].row=-1;offset[3].col=0;
	int num=4,n=0;
	queue <position> q;
	for(i=1;i<=m;i++)
		for(j=1;j<=m;j++)
		{
			if(p[i][j]==1)
			{
				p[i][j]=2;
				here.row=i;
				here.col=j;
				do{
					for(int t=0;t<num;t++)
					{
						nbr.row=here.row+offset[t].row;
			            nbr.col=here.col+offset[t].col;
			            if(p[nbr.row][nbr.col]==1)
						{
							p[nbr.row][nbr.col]=2;
							q.enqueue(nbr);
						}
					}
					if(q.empty()) break;
					q.dequeue(here);
				}while(true);
				n++;
			}
		}
	out<<n<<endl;
	return 0;
}