pex8_12.cpp

数据结构C++代码,经典代码,受益多多,希望大家多多支持

#include <iostream.h>
#pragma hdrstop

#include "set.h"

// a queen is at squrare (rowq,colq). assign all squares to
// which the queen can move to set Board
void ComputeQueenPositions(Set<int>& Board, int rowq, int colq)
{
	int row, col;
	
	// add all positions in the queen's row
	for(col=0;col < 8;col++)
		Board.Insert(8*rowq+col);

	// add all positions in the queen's column
	for(row=0;row < 8;row++)
		Board.Insert(8*row+colq);

	// add all positions on diagonal downward to right
	for (row=0;row < 8;row++)
	{
		col = row + (colq-rowq);
		// reject a square not on the board
		if (col >= 0 && col <= 7)
			Board.Insert(8*row+col);
	}
	
	// add all positions on diagonal upward to right
	for (row=0;row < 8;row++)
	{
		col = -row + (rowq+colq);
		// reject a square not on the board
		if (col >= 0 && col <= 7)
			Board.Insert(8*row+col);
	}
}

// a queen is at square (QRow,QCol), and the squares to
// which it can move are in set Queen. another queen is at
// square (QOtherRow,int QOtherCol). print the board by
// placing an 'X' at any position to which the queen at
// square (QRow,QCol) can move and a blank at the others.
// put a 'Q' at a position containing either queen
void PrintQueenPositions(Set<int> Queen,int QRow,int QCol,
						 int QOtherRow,int QOtherCol)
{
	int row, col;
	const char QueenPos = 'X';
	
	// print the column labels
	cout << "   0 1 2 3 4 5 6 7\n";
	// cycle through the rows of the board
	for(row=0;row < 8;row++)
	{
		// print the row number at the start of each row
		cout << row << " ";
		for(col=0;col < 8;col++)
		{
			// print a 'Q' if we are at the position of the
			// other queen
			if (row == QOtherRow && col == QOtherCol)
					cout << " Q";
			else
			// are we at a square to which the first queen
			// can move?
			if (Queen.IsMember(8*row+col))
				// print 'Q' if we are at first queen's square
				if(row == QRow && col == QCol)
					cout << " Q";
				else
					// print an 'X'
					cout << " " << QueenPos;
			else
				// first queen cannot move here, and second
				// queen is not here. print blank
				cout << "  ";
		}
		cout << endl;
	}
}

// are the queens at squares (Q1Row,Q1Col) and (Q2Row,Q2Col)
// attacking?
int AttackingQueens(int Q1Row, int Q1Col, int Q2Row, int Q2Col)
{	
	// the queens are attacking if they are in the same row
	if (Q1Row == Q2Row)
		return 1;

	// the queens are attacking if they are in the same column
	if (Q1Col == Q2Col)
		return 1;

	// if the queens are on the same diagonal, they are attacking 
	if (Q2Row-Q1Row == Q2Col-Q1Col || Q2Col-Q1Col == Q1Row-Q2Row)
		return 1;
	else
		return 0;
}

void main(void)
{
	// Queen1,Queen2 will contain all the positions to which
	// queens 1 and 2 can move
	Set<int> Queen1(64), Queen2(64);
	int Q1Row,Q1Col,Q2Row,Q2Col;
	
	// input the positions of the two queens
	cout << "Enter the position of one queen: ";
	cin >> Q1Row >> Q1Col;
	cout << "Enter the position of the other queen: ";
	cin >> Q2Row >> Q2Col;
		
	// compute the squares to which each queen can move
	ComputeQueenPositions(Queen1, Q1Row, Q1Col);
	ComputeQueenPositions(Queen2, Q2Row, Q2Col);
	
	// print the board, indicating each position to which
	// the first queen can move
	cout << "Attacking Positions for Queen 1(" << Q1Row 
				<< ',' << Q1Col << ")\n\n";
	PrintQueenPositions(Queen1, Q1Row, Q1Col, Q2Row, Q2Col);
	cout << endl;
	
	// print the board, indicating each position to which
	// the second queen can move
	cout << "Attacking Positions for Queen 2(" << Q2Row 
				<< ',' << Q2Col << ")\n\n";
	PrintQueenPositions(Queen2, Q2Row, Q2Col, Q1Row, Q1Col);
	cout << endl;
	
	// determine whether the queens are attacking
	if (AttackingQueens(Q1Row, Q1Col, Q2Row, Q2Col))
		cout << "The queens are attacking\n";
	else
		cout << "The queens are non-attacking\n";
}

/*
<Run #1>

Enter the position of one queen: 1 5
Enter the position of the other queen: 5 1
Attacking Positions for Queen 1(1,5)

   0 1 2 3 4 5 6 7
0          X X X  
1  X X X X X Q X X
2          X X X  
3        X   X   X
4      X     X    
5    Q       X    
6  X         X    
7            X    

Attacking Positions for Queen 2(5,1)

   0 1 2 3 4 5 6 7
0    X         X  
1    X       Q    
2    X     X      
3    X   X        
4  X X X          
5  X Q X X X X X X
6  X X X          
7    X   X        

The queens are attacking

<Run #2>

Enter the position of one queen: 1 5
Enter the position of the other queen: 4 1
Attacking Positions for Queen 1(1,5)

   0 1 2 3 4 5 6 7
0          X X X  
1  X X X X X Q X X
2          X X X  
3        X   X   X
4    Q X     X    
5    X       X    
6  X         X    
7            X    

Attacking Positions for Queen 2(4,1)

   0 1 2 3 4 5 6 7
0    X       X    
1    X     X Q    
2    X   X        
3  X X X          
4  X Q X X X X X X
5  X X X          
6    X   X        
7    X     X      

The queens are non-attacking
*/