В одной стране есть несколько аэропортов, между некоторыми аэропортами есть рейсы. Можно перелететь из любого аэропорта в любой другой, возможно, с несколькими пересадками. Для каждой пары аэропортов существует только одна последовательность рейсов, соединяющая эти аэропорты.
Два террориста играют в игру. Они делают ходы по очереди. Каждый ход заключается в следующих действиях. Игрок минирует аэропорт, выбирает рейс и улетает вместе со своим коллегой. После взлёта он активирует радиоуправляемый взрыватель. В результате аэропорт, который только что покинули террористы, разрушен, и рейсы в этот аэропорт и из него больше невозможны. После того, как самолёт приземляется, другой игрок делает ход — и дальше по очереди. Проигрывает тот, кто не может сделать ход.
Напишите программу, которая по начальному списку полётов и номеру аэропорта, в котором террористы начинают игру, определяет, кто выигрывает, если террористы играют идеально (каждый выбирает лучший ход).
Входные данные
Первая строка содержит два целых числа: n и k, разделённые пробелом. Здесь n — количество аэропортов (n ≤1000), а k — номер аэропорта, являющегося начальной точкой игры (1 ≤ k ≤ n). Следующая n−1 строка содержит пары целых чисел, разделённых пробелами. Это номера аэропортов, соединённых рейсом. Все рейсы двусторонние и упомянуты только один раз. Каждый аэропорт соединён рейсами не более, чем с 20 другими.
Выходные данные
Если игрок, начинающий игру, выигрывает, программа должна написать «First player wins flying to airport L«, где L— номер аэропорта, в который игрок должен вылететь из текущего. Если таких аэропортов несколько, программа должна выбрать вариант с меньшим номером аэропорта. Если начинающий игрок проигрывает, программа должна написать «First player loses«.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
#include <cstdlib> #include <iostream> #include <vector> #include <algorithm> using namespace std; bool is_use[1001]; vector<int> airports[1001]; int level = 0; // уровень вложенности dfs /*int isFindAnsver = false; // переменная выхода из цикла*/ int second_ver = 0; // переменная запоминает вторую вершину, для ответа bool is_second_ver_find = false; bool is_sort[1001]; bool FIRST_WIN = true, SECOND_WIN = false; bool dfs(int now_ver){ // Возвращает true если выигрывает первы, и false, если второй is_use[now_ver] = true; bool child; level++; if(level == 2){ second_ver = now_ver; } if(!is_sort[now_ver]){ sort(airports[now_ver].begin(), airports[now_ver].end()); is_sort[now_ver] = true; } int count_ver=0; // переменная считает вершины в которые можно пойти из данной for(int i=0 ; i<airports[now_ver].size() ; i++ ){ // if( !is_use[ airports[now_ver][i] ] ){ // В зависимости от четноси мы должны искать тот ли иной овет // от четности зависит то каккой игрок ходит на данный момент child = dfs(airports[now_ver][i]); // Если нечетное, то мы ищем правильных ход первого, иначе правильный ход второго if(level%2 == 1? child == FIRST_WIN : child == SECOND_WIN){ if(level == 1){ if(child == FIRST_WIN){ cout << "First player wins flying to airport " << second_ver << endl; }else{ // SECOND_WIn cout << "First player loses" << endl; } return true; }else{ level--; return child; } } // если найден нужный нам ответ на этом уровне count_ver++; } } is_use[now_ver] = false; if(level != 1)return ((level--)%2 == 1? SECOND_WIN : FIRST_WIN); else{ if(child == FIRST_WIN){ cout << "First player wins flying to airport " << second_ver << endl; }else{ cout << "First player loses" << endl; } } } int main(){ int n, k; cin >> n >> k; int u, v; for( int i=0 ; i<n-1 ; i++ ){ cin >> u >> v; airports[u].push_back(v); airports[v].push_back(u); } second_ver = k; dfs(k); } |
Если оно равно нулю то это тупик.
И мы посмотрим кто бы выиграл если бы бандиты дошли до этого аэропорта.Если level нечетный, то мы ищем правильный ход первого, иначе второго террориста. Если уровень равен 1, то мы уже выходим. Выводим ответ. Иначе, если level не равен 1, то мы еще не дошли до конца и возвращаем выше, кто выигрывает в данном узле.
При этом каждый бандит ищет ветку где бы он победил.
Определяем количество детей. Если мы не в тупике, то но увеличивается на 1. Далее, если ходит второй террорист, то он выбирает ветку, в котором выиграет он. Если мы попали в тупик, выводим кто выиграл в зависимости от четности пройденного пути.
В main() считываем количество аэропортов и номер первого , записываем в вектора смежные аэропорты для каждого и запоминаем первую вершину. Запускаем dfs().
Не очень хорошо получилось. Весьма сумбурное объяснение.
— вместо коментариев при объявлении переменных Вы просто в объяснении перечисляете, что хранят переменные без указания их имени. Как понять какое объяснение относится к какой переменной?
— много синтаксических ошибок, особенно в комментариях
— оценка 4 из двадцати возможных (4 = 20 — 16)
Жалко, что большая работа становится бесполезной для читателей из-за небрежного объяснения.
P.S. Решение может быть вдвое лаконичнее.