А 1041

Задача. Найти такую расстановку восьми слонов на шахматной доске, при которой каждое поле будет находиться под ударом одного из них.

Предполагается, что используется обычная шахматная доска размером 8х8, а слоны могут бить по
обоим частичным диагоналям на пересечении которых они находятся. Если на той же диагонали находится ещё один слон, то он перекрывает линию боя. Для данной задачи этот факт не имеет значения, поскольку требуется, чтобы каждую клетку бил хотя бы один слон. Перекрытые клетки диагонали будут находиться под боем того слона, который перекрывает линию боя.

#include <iostream>
#include <cstdlib>

using namespace std;

const int COUNT_EL = 8, WIDTH = 8, HEIGHT = 8;
const bool SET_DIA = true, DEL_DIA = false;
int a[HEIGHT][WIDTH];				// доска
bool is_set[HEIGHT][WIDTH];			// Расположение слонов на доске
int count_null = WIDTH * HEIGHT;		// Количество пустых клеток
bool isEnd = false;				// Флаг выхода из рекурсии
const bool FIRST = true, SECOND = false;	// флаги для индификации диагоналей

int diagonal(bool is_firstD, bool set, int x, int y, int i, int j){ // осуществляет все операции с диагоналями
	while(y<HEIGHT && (is_firstD? (x<WIDTH) : (x >= 0))){					// заполняем/очищаем первую\вторую диагональ
		if(is_firstD? true : x != j || y != i){
			if(set){							  
				a[y][x]++;
				if(a[y][x] == 1){				
					count_null--;
				}
			}else{								  
				a[y][x]--;
				if(a[y][x] == 0){					
					count_null++;
				}
			}
		}
		x += (is_firstD? 1 : -1);
		y++;
	}
}

int space(bool set, int level, int i, int j){	// функция осуществляет операции с диагоналями (установку \ удаление)
	is_set[i][j] = set;			// Сохраняем последнее расположение слонов
	int x, y;
	if(j>i){	// ищем начало прохода первой диагонали (параллельной или идентичной главной)
		y = 0;
		x = j-i;
	}else{
		x = 0;
		y = i-j;
	}
	diagonal(FIRST, set, x, y, i, j);
	// ищем начало второй диагонали (перпендикулярной главной (побочной))
	int sum = i+j;
	if(sum < WIDTH){
		x = sum;
		y = 0;
	}else{
		x = WIDTH-1;
		y = sum-x;
	}
	diagonal(SECOND, set, x, y, i, j);
}

bool find_permutation(int level=0){		
	level++;

	for(int i = level-1, j = (level==1?1:0); j < WIDTH ; j++){			
	/*экспериментально было замечено, что при установки первого слона в самом начале строки нужных нам последовательностей найдено не будет
	  именно по этой причине, если мы задаем первого слона, то начинаем со второй ячейки строки 
	*/
		if(a[i][j] == 0){			
			space(SET_DIA, level, i, j);							// устанавливаем слона и поле под его боем 
			if(level != COUNT_EL){											
				find_permutation(level);											
				if(isEnd){						
					return false;
				}
			}else if(count_null == 0){					  
				cout << "Ответ найден:"<< endl << endl;			
				for( int i1=0 ; i1<HEIGHT ; i1++ ){			
					for( int j1=0 ; j1<WIDTH ; j1++ ){
						cout << (is_set[i1][j1]? 1 : 0) << (j1+1 == WIDTH ? '\n' : ' ' );
					}
				}
				isEnd = true;						
				return false;						
			}
			space(DEL_DIA, level, i, j);// удаляем слона и поле под его боем 							
		}
	}
	level--;
}

int main(){
	find_permutation();
}

#include <iostream>

#include <cstdlib>

using namespace std;

const int COUNT_EL = 8, WIDTH = 8, HEIGHT = 8;

const bool SET_DIA = true, DEL_DIA = false;

int a[HEIGHT][WIDTH]; // доска

bool is_set[HEIGHT][WIDTH]; // Расположение слонов на доске

int count_null = WIDTH * HEIGHT; // Количество пустых клеток

bool isEnd = false; // Флаг выхода из рекурсии

const bool FIRST = true, SECOND = false; // флаги для индификации диагоналей

int diagonal(bool is_firstD, bool set, int x, int y, int i, int j){ // осуществляет все операции с диагоналями

while(y<HEIGHT && (is_firstD? (x<WIDTH) : (x >= 0))){ // заполняем/очищаем первую\вторую диагональ

if(is_firstD? true : x != j || y != i){

if(set){

a[y][x]++;

if(a[y][x] == 1){

count_null--;

}

}else{

a[y][x]--;

if(a[y][x] == 0){

count_null++;

}

x += (is_firstD? 1 : -1);

y++;

}

int space(bool set, int level, int i, int j){ // функция осуществляет операции с диагоналями (установку \ удаление)

is_set[i][j] = set; // Сохраняем последнее расположение слонов

int x, y;

if(j>i){ // ищем начало прохода первой диагонали (параллельной или идентичной главной)

y = 0;

x = j-i;

}else{

x = 0;

y = i-j;

}

diagonal(FIRST, set, x, y, i, j);

// ищем начало второй диагонали (перпендикулярной главной (побочной))

int sum = i+j;

if(sum < WIDTH){

x = sum;

y = 0;

}else{

x = WIDTH-1;

y = sum-x;

}

diagonal(SECOND, set, x, y, i, j);

}

bool find_permutation(int level=0){

level++;

for(int i = level-1, j = (level==1?1:0); j < WIDTH ; j++){

/*экспериментально было замечено, что при установки первого слона в самом начале строки нужных нам последовательностей найдено не будет

именно по этой причине, если мы задаем первого слона, то начинаем со второй ячейки строки

if(a[i][j] == 0){

space(SET_DIA, level, i, j); // устанавливаем слона и поле под его боем

if(level != COUNT_EL){

find_permutation(level);

if(isEnd){

return false;

}

}else if(count_null == 0){

cout << "Ответ найден:"<< endl << endl;

for( int i1=0 ; i1<HEIGHT ; i1++ ){

for( int j1=0 ; j1<WIDTH ; j1++ ){

cout << (is_set[i1][j1]? 1 : 0) << (j1+1 == WIDTH ? '\n' : ' ' );

}

isEnd = true;

return false;

}

space(DEL_DIA, level, i, j);// удаляем слона и поле под его боем

}

level--;

}

int main(){

find_permutation();

}

Определяем переменные: количество слонов, длинна и ширина шахматного поля, массив клеток поля. Далее определяем булевы переменные для добавления и удаления диагоналей, расположения слонов, выхода из рекурсии. Функция «giagonal» осуществляет все операции с диагоналями. Добавляет/удаляет диагонали(параллельные главной или побочной). Она принимает булевы переменные для определения того, добавляем мы главную диагональ или побочную, собираемся мы добавлять диагональ или удалять. А также координаты начала диагоналей, координаты расположения слона. Если клетку бьет какой-либо слон, прибавляем к ее значению 1. При этом число свободных клеток уменьшается. Если же мы удаляем диагональ, то просто уменьшаем количество бьющих данную клетку слонов (это указывается в самой клетке). Если удаленный слон был единственным, кто ее бил, увеличиваем число свободных клеток. Функция «space». Она используется как для удаления, так и для добавления диагоналей. В ней мы запоминаем последнее расположение слонов на доске и далее ищем начало прохода диагоналей. Для этого сначала мы определяем в какой части доски находится поставленный слон и исходя из этого, если оказалось, что координата по горизонтали больше координаты по вертикали, то следовательно начало первой диагонали будет в первой строке, в противном случае ее начало будет в первом столбце. Вторые координаты зависят от разности j-i. При поиске начала второй диагонали используем сумму i+j, если эта сумма меньше 8 (то есть слон находится ближе к верхнему левому углу доски, чем к правому нижнему) тогда диагональ начинается в первом столбце. Функция «find_permutation» (рекурсивно расставляет слонов). С каждой новым поставленным слоном увеличиваем переменную level, для определения в последствии момента установки последнего слона. Просматриваем клетки, если какая-то из них не под боем-ставим туда слона и запускаем функцию «space» для него. Так расставляем их, пока число слонов не достигнет 8. Если после какой-либо расстановки мы нашли правильный ответ, то используя булеву переменную isEnd выходим из рекурсии. Если после установки восьмого слона оказалось, что все поля были заполнены, то мы выводим: «Ответ найден» и печатаем доску (если булева переменная is_set — true, то есть этот элемент слон, тогда выводим 1, остальные клетки — 0). Далее выходим из всех циклов, определив переменную isEnd = true. Удаляем слонов и битые ими поля. Конец программы.

ideone.com

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

А 1041

Related Images:

Понравилось это:

Похожее

One thought on “А 1041”

Добавить комментарий Отменить ответ

Related Images:

Share this:

Понравилось это:

Похожее

One thought on “А 1041”

Добавить комментарий Отменить ответ