image.cpp

FZU 大二 的数据结构与算法 老师出的题目的优秀作业 第2到第5章

#include<iostream>
#include<fstream>
using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");


class OutOfBounds{
public:
	OutOfBounds(){}
};

template<class T>class Queue;
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); }
		bool Full()const;
		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>
bool Queue<T>::Full()const
{
	Node<T>*p;
	try{
		p=new Node<T>;
		delete p;
		return false;
	}
	catch(NoMem){return true;}
}

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)
{
	if(Empty())throw OutOfBounds();
	x=front->data;
	Node<T>*p=front;
	front=front->next;
	delete p;
	return *this;
}

class Position
{
public:
	Position(){row=col=0;}
	~Position(){}
	int row;//行
	int col;//列
};

int main()
{

	int m;
	in>>m;
	int **array;
	array=new int*[m+2];
	for(int i=0;i<m+2;i++)
		array[i]=new int[m+2];
	for(i=0;i<=m+1;i++)//设阵列“围墙”
	{
		array[0][i]=array[m+1][i]=0;
		array[i][0]=array[i][m+1]=0;
	}
	for(i=1;i<=m;i++)
		for(int j=1;j<=m;j++)
			in>>array[i][j];

    Position offset[4];
	offset[0].row=0; offset[0].col=1;//right
	offset[1].row=1; offset[1].col=0;//below
	offset[2].row=0; offset[2].col=-1;//left
	offset[3].row=-1;offset[3].col=0;//above

	int NumOfNbs=4;  int n=0;
	Position here,nbr;

	for(i=1;i<=m;i++)
		for(int j=1;j<=m;j++)
		{
			if(array[i][j]==1)
			{
				here.row=i;
			    here.col=j;
				array[here.row][here.col]=0;
				Queue<Position>Q;
				do{
					for(int k=0;k<NumOfNbs;k++)
					{
						nbr.row=here.row+offset[k].row;
						nbr.col=here.col+offset[k].col;
						if(array[nbr.row][nbr.col]==1)
						{
							array[nbr.row][nbr.col]=0;//标记后，变为0
							Q.EnQueue(nbr);
						}
					}
					if(Q.Empty()==1) break;
					Q.DeQueue(here);
				}while(true);
				n++;
			}
		}
		
		out<<n<<endl;
		for(int h=0;h<m+2;h++)
			delete[]array[h];
		delete[]array;
		array=0;
		return 0;
}