Информатика: Расстановка шахматных фигур — различия между версиями

  1 #include <iostream>
  2 #include <math.h>
  3 #include <cmath>
  4 
  5 using namespace std;
  6 
  7 int n,type, *a, *stak, variant, maxst = 0;
  8 
  9 void king(int x, int &top)                      //отметить битые клетки королем
 10 {
 11     // 012
 12     // 345
 13     // 678
 14 
 15     //0
 16     if (((x % n) > 1) && ((x / n) > 1))
 17     {
 18         int ii = x - n - 1;
 19         if (a[ii] != -2)
 20         {
 21             a[ii]++;
 22             stak[top] = ii;
 23             top++;
 24         }
 25     }
 26 
 27     //1
 28     if ((x / n) > 0)
 29     {
 30         int ii = x - n;
 31         if (a[ii] != -2)
 32         {
 33             a[ii]++;
 34             stak[top] = ii;
 35             top++;
 36         }
 37     }
 38 
 39     //2
 40     if (((x % n) < (n - 1)) && ((x / n) > 0))
 41     {
 42         int ii = x - n + 1;
 43         if (a[ii] != -2)
 44         {
 45             a[ii]++;
 46             stak[top] = ii;
 47             top++;
 48         }
 49     }
 50 
 51     //3
 52     if ((x % n) > 0)
 53     {
 54         int ii = x - 1;
 55         if (a[ii] != -2)
 56         {
 57             a[ii]++;
 58             stak[top] = ii;
 59             top++;
 60         }
 61     }
 62 
 63     //5
 64     if ((x % n) < (n - 1))
 65     {
 66         int ii = x + 1;
 67         if (a[ii] != -2)
 68         {
 69             a[ii]++;
 70             stak[top] = ii;
 71             top++;
 72         }
 73     }
 74 
 75     //6
 76     if (((x % n ) > 0) && ((x / n) < (n - 1)))
 77     {
 78         int ii = x + n - 1;
 79         if (a[ii] != -2)
 80         {
 81             a[ii]++;
 82             stak[top] = ii;
 83             top++;
 84         }
 85     }
 86 
 87     //7
 88     if ((x / n ) < (n - 1))
 89     {
 90         int ii = x + n;
 91         if (a[ii] != -2)
 92         {
 93             a[ii]++;
 94             stak[top] = ii;
 95             top++;
 96         }
 97     }
 98 
 99     //8
100     if (((x % n ) < (n - 1)) && ((x / n) < (n - 1)))
101     {
102         int ii = x + n + 1;
103     if (a[ii] != -2)
104         {
105             a[ii]++;
106             stak[top] = ii;
107             top++;
108         }
109     }
110 }
111 
112 void bishop(int x, int &top)                                                              //отметить битые клетки слоном
113 {
114     //вверх влево
115     for (int i = (x - (n + 1)); ((i >= 0) && ((i%n) != (n-1))); i -= (n+1))
116     {
117         if (a[i] != -2)
118         {
119             a[i]++;
120             stak[top] = i;
121             top++;
122         }
123     }
124 
125     //вниз вправо
126     for (int i = (x + (n + 1)); ((i < n*n) && ((i%n) != 0)); i += (n+1))
127     {
128         if (a[i] != -2)
129         {
130             a[i]++;
131             stak[top] = i;
132             top++;
133         }
134     }
135 
136     //вверх вправо
137     for (int i = x - (n - 1); ((i >= 0) && ((i%n) != 0)); i -= (n-1))
138     {
139         if (a[i] != -2)
140         {
141             a[i]++;
142             stak[top] = i;
143             top++;
144         }
145     }
146 
147     //вниз влево
148     for (int i = x + (n - 1); ((i < n*n) && ((i%n) != (n-1))); i += (n-1))
149     {
150         if (a[i] != -2)
151         {
152             a[i]++;
153             stak[top] = i;
154             top++;
155         }
156     }
157 }
158 
159 void knight(int x, int &top)                                            //отметить битые клетки конем
160 {
161     if (((x%n) > 0) && (x/n) > 1)
162     {
163         int ii = x - 2*n - 1;
164         if (a[ii] != -2)
165         {
166             a[ii]++;
167             stak[top] = ii;
168             top++;
169         }
170     }
171 
172     if (((x%n) > 1) && (x/n) > 0)
173     {
174         int ii = x - n - 2;
175         if (a[ii] != -2)
176         {
177             a[ii]++;
178             stak[top] = ii;
179             top++;
180         }
181     }
182 
183     if (((x%n) > 1) && (x/n) < (n - 1))
184     {
185         int ii = x + n - 2;
186         if (a[ii] != -2)
187         {
188             a[ii]++;
189             stak[top] = ii;
190             top++;
191         }
192     }
193 
194     if (((x%n) > 0) && (x/n) < (n - 2))
195     {
196         int ii = x + 2*n - 1;
197         if (a[ii] != -2)
198         {
199             a[ii]++;
200             stak[top] = ii;
201             top++;
202         }
203     }
204 
205     if (((x%n) < (n - 1)) && (x/n) < (n - 2))
206     {
207         int ii = x + 2*n + 1;
208         if (a[ii] != -2)
209         {
210             a[ii]++;
211             stak[top] = ii;
212             top++;
213         }
214     }
215 
216     if (((x%n) < (n - 2)) && (x/n) < (n - 1))
217     {
218         int ii = x + n + 2;
219         if (a[ii] != -2)
220         {
221             a[ii]++;
222             stak[top] = ii;
223             top++;
224         }
225     }
226 
227     if (((x%n) < (n - 2)) && (x/n) < 0)
228     {
229         int ii = x - n + 2;
230         if (a[ii] != -2)
231         {
232             a[ii]++;
233             stak[top] = ii;
234             top++;
235         }
236     }
237 
238     if (((x%n) < (n - 1)) && (x/n) < 1)
239     {
240         int ii = x - 2*n + 1;
241         if (a[ii] != -2)
242         {
243             a[ii]++;
244             stak[top] = ii;
245             top++;
246         }
247     }
248 }
249 
250 void rook(int x, int &top)                                                      //отметить битые клетки ладьей
251 {
252     int k = x - (x % n);
253     while ((k/n) == (x/n))
254     {
255 
256         if ((k != x) && (a[k] != -2))
257         {
258             a[k]++;
259             stak[top] = k;
260             top++;
261         }
262         k ++;
263     }
264 
265     k = (x % n);
266     while (((k/n)) != n)
267     {
268         if ((k != x) && (a[k] != -2))
269         {
270             a[k]++;
271             stak[top] = k;
272             top++;
273         }
274         k += n;
275     }
276 
277 }
278 void set_figure(int x, int &top)                                    //ставим фигуры на доску
279 {
280     //отмечаем "битые" клетки
281     switch (type)
282     {
283 		//король
284         case 1:
285         {
286             king(x,top);
287             break;
288         }
289 
290 		//слон
291 		case 2:
292 		{
293 		    bishop(x,top);
294             break;
295 		}
296 
297 		//конь
298 		case 3:
299 		{
300 		    knight(x,top);
301 			break;
302 		}
303 		//ладья
304         case 4:
305         {
306             rook(x,top);
307             break;
308         }
309         //ферзь
310         case 5:
311         {
312             rook(x,top);
313             bishop(x,top);
314             break;
315         }
316     }
317 
318     //отмечаем,что в данной клетке стоит фигура
319 	a[x] = -1;
320     stak[top] = x;
321     top++;
322 }
323 
324 void step(int top,int x,int st)
325 {
326 	int xtop = top;
327 	switch (variant)
328 	{
329 		case 1:
330 		{
331 			if (st != (n - 1))
332 			{
333 				set_figure(x,top);
334 				for (int i = 0; i < (n*n); i++)
335 					if (a[i] == 0)
336 						step(top,i,st + 1);
337 			}
338 			else[[:File:Шахматы.rar]]
339 			{
340 				set_figure(x,top);
341                 cout << endl;
342 				for (int i = 0; i < (n*n); i++)
343 				{
344 					cout.width(3);
345 					if (((i % n) == 0) && (i != 0))
346 						cout << endl;
347 					if (a[i] == -1)
348 						cout << 1;
349 					else
350 						cout << 0;
351 				}
352 				cout << endl;
353 			}
354 			break;
355 		}
356 		case 2:
357 		{
358 			set_figure(x,top);
359 			if ((st+1) > maxst)
360 				maxst = st + 1;
361 			for (int i = 0; i < (n*n); i++)
362 				if (a[i] == 0)
363 					step(top,i,st+1);
364 			break;
365 		}
366 	}
367 
368 
369 
370 // обратный ход
371     for (int i = xtop; i < top; i++)
372     {
373         if ((a[stak[i]] != -1) && (a[stak[i]] != -2))
374             a[stak[i]]--;
375         else
376             //не забываем отметить,что фигура уже здесь стояла(чтобы избежать повторов)
377             if (a[stak[i]] == -1)
378                 a[stak[i]] = -2;
379  //       cerr << " Back "  << stak[i] << endl;
380     }
381 }
382 
383 int main()
384 {
385 
386     //cin >> n >> type >> variant;
387     n = 5;
388     type = 4;
389 	variant = 1;
390     a    = new int[n*n];
391     stak = new int[n*n*4];
392 
393     for (int i = 0; i < (n*n); i++)
394     {
395         for (int j = 0; j < (n*n); j++)
396             a[j] = 0;
397         if (variant == 1)
398             cout << "__________________________________" << endl;
399         step(0,i,0);
400     }
401 	if (variant == 2)
402 	  cout << maxst;
403     return 0;
404 }

  1 #include <iostream>
  2 #include <algorithm>
  3 #include <exception>
  4 #include <string>
  5 #include <algorithm>
  6 
  7 //пусть для определенности максимальный размер доски - 128 клеток
  8 #define MAX_SIZE 128
  9 
 10 // перечисление для определения типа фигуры
 11 enum figure_type
 12 {
 13     KING,
 14     QUEEN,
 15     ROOK,
 16     BISHOP,
 17     KNIGHT
 18 };
 19 
 20 // класс для создания доски и расстановки фигур
 21 class chess_board
 22 {
 23 public:
 24     // конструктор (принимает только размеры)
 25     chess_board(const int &size)
 26     {
 27         if (size >= 0 && size <= MAX_SIZE)
 28         {
 29             size_ = size;
 30             clean_board();
 31         }
 32 
 33         else
 34         {
 35             std::cout << "wrong size" << std::endl;
 36             throw std::string("wrong size");
 37         }
 38     }
 39 
 40 
 41     // функция очистки доски (занулить все клетки)
 42     void clean_board()
 43     {
 44         //обнулить счетчик количества фигур на доске
 45         figures_on_board_ = 0;
 46         //присвоить всем клеткам значение 0
 47         for (int i = 0; i < size_; ++i)
 48         {
 49             for (int j = 0; j < size_; ++j)
 50             {
 51                 board_[i][j] = 0;
 52             }
 53         }
 54     }
 55 
 56     // функция, принимающая размер доски
 57     int get_size()
 58     {
 59         return size_;
 60     }
 61     // функция, обновляющая количество фигур на доске
 62     int get_figures_number()
 63     {
 64         return figures_on_board_;
 65     }
 66 
 67     //функция, пытающаяся поставить фигуру на свободное место и возвращающая
 68     //истину в случае успеха и ложь в случае неудачи
 69     bool put_figure (const figure_type& figure, const int& x, const int& y, const int& step)
 70     {
 71         if (board_[x][y] > 0 || board_[x][y] < -step)
 72         {
 73            //если здесь уже стоит фигура или мы когда-то пытались ее сюда поставить, вернуть ложь
 74             return false;
 75         }
 76 
 77         if (check_figure(figure, x, y))
 78         {
 79             board_[x][y] = step;
 80             ++figures_on_board_;
 81             return true;
 82         }
 83         else
 84         {
 85             return false;
 86         }
 87     }
 88 
 89     //отметить клетку как ранее пройденную функцией
 90     //вычесть единицу из количества фигур на доске
 91     void remove_figure(const int& x, const int& y)
 92     {
 93         board_[x][y] *= -1;
 94         --figures_on_board_;
 95     }
 96 
 97     //функция печати доски на экран
 98     void print() const
 99     {
100         using namespace std;
101         cout << "==========================================" << endl;
102         for (int i = 0; i < size_; ++i)
103         {
104             for (int j = 0; j < size_; ++j)
105             {
106                 //если фигура стоит в клетке, то вывести "*", если нет - вывести "-"
107                 cout << (board_[i][j] > 0?"*":"-") << " ";
108             }
109             cout << endl;
110         }
111         cout << "==========================================" << endl;
112     }
113 
114 private:
115 
116     //функция, проверяющая возможность или невозможность постановки фигуры на данную клетку
117     bool check_figure(const figure_type& figure, const int& x, const int& y)
118     {
119         //выбор следующего действия в зависимости от типа фигуры
120         switch (figure)
121         {
122             case KING:
123                 return check_king(x, y);
124             case QUEEN:
125                 return check_queen(x, y);
126             case ROOK:
127                 return check_rook(x, y);
128             case BISHOP:
129                 return check_bishop(x, y);
130             case KNIGHT:
131                 return check_knight(x, y);
132                 //в случае ошибки ввода вернуть ложь
133             default:
134                 return false;
135         }
136     }
137 
138     //поиск расстановок короля
139     bool check_king(const int& x, const int& y)
140     {
141         int min_x = std::max(x - 1, 0);
142         int max_x = std::min(x + 1, size_ - 1);
143         int min_y = std::max(y - 1, 0);
144         int max_y = std::min(y + 1, size_ - 1);
145 
146         for (int i = min_x; i <= max_x; ++i)
147         {
148             for (int j = min_y; j <= max_y; ++j)
149             {
150                 if (board_[i][j] > 0)
151                 {
152                     return false;
153                 }
154             }
155         }
156         return true;
157     }
158 
159     //поиск расстановок ладьи
160     bool check_rook(const int& x, const int& y)
161     {
162         for (int i = 0; i < size_; ++i)
163         {
164             if (board_[i][y] > 0)
165             {
166                 return false;
167             }
168         }
169         for (int j = 0; j < size_; ++j)
170         {
171             if (board_[x][j] > 0)
172             {
173                 return false;
174             }
175         }
176         return true;
177     }
178 
179     //поиск расстановок слона
180     bool check_bishop(const int& x, const int& y)
181     {
182         bool check = true;
183 
184         int k_start_1 = -std::min(x, y);
185         int k_end_1 = std::min( size_ - x, size_ - y) - 1;
186 
187         int k_start_2 = -std::min( x, size_ - y - 1);
188         int k_end_2 = std::min( y, size_ - x - 1);
189 
190 
191         for (int k = k_start_1; k <= k_end_1; ++k)
192         {
193             check = check_coord(x + k, y + k) && check ;
194         }
195         for (int k = k_start_2; k <= k_end_2; ++k)
196         {
197             check = check_coord(x + k, y - k) && check;
198         }
199 
200         return check;
201     }
202 
203 
204     //поиск расстановок коня
205     bool check_knight(const int& x, const int& y)
206     {
207         bool check =
208             check_coord(x - 2, y - 1) &&
209             check_coord(x - 2, y + 1) &&
210             check_coord(x - 1, y - 2) &&
211             check_coord(x - 1, y + 2) &&
212             check_coord(x + 1, y - 2) &&
213             check_coord(x + 1, y + 2) &&
214             check_coord(x + 2, y - 1) &&
215             check_coord(x + 2, y + 1);
216         return check;
217     }
218 
219     //поиск расстановок королевы
220     bool check_queen(const int& x, const int& y)
221     {
222         return check_rook(x, y) && check_bishop(x, y);
223     }
224 
225    //функция поиска расстановок, в случае, когда на доске что-то стоит, вернуть ложь
226    //иначе поставить вернуть истину
227     bool check_coord(const int& x, const int& y)
228     {
229         if (x >= 0 && x < size_ && y >= 0 && y < size_)
230         {
231             if (board_[x][y] > 0)
232             {
233                 return false;
234             }
235         }
236         return true;
237     }
238 
239     // if board_[x][y] == 0
240     //     клетка свободна
241     // if board_[x][y] == s
242     //     фигура была поставлена на шаге S
243     // if board_[x][y] == -s
244     //     клетка свободна, но была попытка поставить фигуру на шаге S
245     int board_[MAX_SIZE][MAX_SIZE];
246     int size_;
247     int figures_on_board_;
248 };
249 
250 //функция расчета максимума для любой доски в зависимости от типа фигуры
251 int get_max_figures (const figure_type& figure, const int& size)
252 {
253     switch (figure)
254     {
255         case KING:
256             return (size + 1) / 2;
257         case QUEEN:
258             if (size <= 2)
259             {
260                 return 1;
261             }
262             else if (size == 3)
263             {
264                 return 2;
265             }
266             else
267             {
268                 return size;
269             }
270         case ROOK:
271             return size;
272         case BISHOP:
273             if (size == 1)
274             {
275                 return size;
276             }
277             else
278             {
279                 return 2 * (size - 1);
280             }
281         case KNIGHT:
282             if (size <= 2)
283             {
284                 return size * size;
285             }
286             else
287             {
288                 return (size * size + 1) / 2;
289             }
290         default:
291             return 1;
292     }
293 }
294 
295 //функция для расстановки максимального числа фигур на доске
296 void place_figures_for_max(chess_board &board, const figure_type& figure, const int& max_figures, int step)
297 {
298     ++step;
299     const int size = board.get_size();
300     for (int i = 0; i < size; ++i)
301     {
302         for (int j = 0; j < size; ++j)
303         {
304             //если мы можем поставить фигуру, то добавляем к максимуму единицу и запускаем цикл снова
305             if (board.put_figure(figure, i, j, step))
306             {
307                 //если число фигур на доске достигло максимума, то вывести доску
308                 if (board.get_figures_number() == max_figures)
309                 {
310                     board.print();
311                 }
312                 //если число фигур не достигло максимума, продолжить выполнение функции
313                 else
314                 {
315                     place_figures_for_max(board, figure, max_figures, step);
316                 }
317                 board.remove_figure(i, j);
318             }
319         }
320     }
321 }
322 
323 //функция, принимающая ввод с клавиатуры как строковый тип данных
324 figure_type get_figure_type(const std::string& str)
325 {
326     using namespace std;
327 
328     figure_type figure;
329     if (str == string("king"))
330     {
331         figure = KING;}
332     else if (str == string("queen"))
333     {
334         figure = QUEEN;}
335     else if (str == string("rook"))
336     {
337         figure = ROOK;
338     }
339     else if (str == string("bishop"))
340     {
341         figure = BISHOP;
342     }
343     else if (str == string("knight"))
344     {
345        figure = KNIGHT;
346     }
347     //вывести ошибку в случае неверного ввода
348     else
349     {
350         cout << "wrong figure type" << endl;
351         throw string("wrong figure type");
352     }
353 
354     return figure;
355 }
356 
357 int main()
358 {
359     //использовать стандартное пространств имен
360     using namespace std;
361 
362     int size;
363     string type_of_figure;
364     string type_of_action;
365     figure_type figure;
366 
367     cout << "Возможные фигуры: king, queen, rook, bishop, knight" << endl;
368     cout << "Возможные действия: max, placing" << endl;
369     cout << "----------------------------------------------------" << endl;
370 
371     cout <<"Введите размер доски: ";
372     cin >> size;
373     chess_board board(size);
374 
375     cout << "Введите тип фигуры: ";
376     cin >> type_of_figure;
377     figure = get_figure_type(type_of_figure);
378 
379     cout << "Введите необходимое действие: ";
380     cin >> type_of_action;
381 
382     if (type_of_action == string("max"))
383     {
384 
385         int max_figures = get_max_figures(figure, size);
386         cout << "Max figures: " << max_figures << endl;
387 
388         cout << "Хотите ли вы просмотреть все варианты? (yes/no) ";
389         string answer;
390         cin >> answer;
391         //если нужно вывести все расстановки, то применить непосредственно функцию поиска расстановок максимума
392         if (answer == string("yes"))
393         {
394             int step = 0;
395             place_figures_for_max(board, figure, max_figures, step);
396         }
397     }
398     //иначе если нужно расставить определенное количество фигур, то применить функцию поиска расстановок
399     //относительно введенного числа
400     else if (type_of_action == string("placing"))
401     {
402         int figures_to_place;
403         cout << "Сколько фигур нужно расставить: ";
404         cin >> figures_to_place;
405 
406         int step = 0;
407         place_figures_for_max(board, figure, figures_to_place, step);
408     }
409     //иначе вывести ошибку действия
410     else
411     {
412         cout << "wrong type of action" << endl;
413         throw string("wrong type of action");
414     }
415 
416     return 0;
417 }