В этой задаче вам необходимо реализовать валидацию корректности карты для стратегической…
- User
В этой задаче вам необходимо реализовать валидацию корректности карты для стратегической компьютерной игры.
Карта состоит из гексагонов (шестиугольников), каждый из которых принадлежит какому-то региону карты. В файлах игры карта представлена как n строк по m символов в каждой (строки и символы в них нумеруются с единицы). Каждый нечетный символ каждой четной строки и каждый четный символ каждой нечетной строки — точка (символ . с ASCII кодом 46 ); все остальные символы соответствуют гексагонам и являются заглавными буквами латинского алфавита. Буква указывает на то, какому региону принадлежит гексагон.
Посмотрите на картинку ниже, чтобы понять, как описание карты в файлах игры соответствует карте из шестиугольников.
Соответствие описания карты в файле (слева) и самой карты (справа). Регионы R, G, V, Y и B окрашены в красный, зеленый, фиолетовый, желтый и синий цвет, соответственно. Вы должны проверить, что каждый регион карты является одной связной областью. Иными словами, не должно быть двух гексагонов, принадлежащих одному и тому же региону, которые не соединены другими гексагонами этого же региона.
На какие задачи похоже по логике решния?
- Assistant
По логике решения данной задачи, оно похоже на задачи на поиск связных компонент графа или на проверку связности графа. В данной задаче гексагоны, принадлежащие одному региону, образуют компоненту связности. Таким образом, необходимо проверить, что для каждого региона компонента связности состоит из всех гексагонов этого региона.
- User
const int N=1000000, // максимальное число вершин в суффиксном дереве INF=1000000000; // константа "бесконечность" string a; // входная строка, для которой надо построить дерево int t[N][26], // массив переходов (состояние, буква) l[N], // левая r[N], // и правая границы подстроки из a, отвечающие ребру, входящему в вершину p[N], // предок вершины s[N], // суффиксная ссылка tv, // вершина текущего суффикса (если мы посередине ребра, то нижняя вершина ребра) tp, // положение в строке соответствующее месту на ребре (от l[tv] до r[tv] включительно) ts, // количество вершин la; // текущий символ строки
void ukkadd(int c) { // дописать к дереву символ c suff:; // будем приходить сюда после каждого перехода к суффиксу (и заново добавлять символ) if (r[tv]<tp) { // проверим, не вылезли ли мы за пределы текущего ребра // если вылезли, найдем следующее ребро. Если его нет - создадим лист и прицепим к дереву if (t[tv][c]==-1) {t[tv][c]=ts;l[ts]=la;p[ts++]=tv;tv=s[tv];tp=r[tv]+1;goto suff;} tv=t[tv][c];tp=l[tv]; // в противном случае просто перейдем к следующему ребру } if (tp==-1 || c==a[tp]-'a') tp++; else { // если буква на ребре совпадает с c то идем по ребру, а иначе // разделяем ребро на два. Посередине - вершина ts l[ts]=l[tv];r[ts]=tp-1;p[ts]=p[tv];t[ts][a[tp]-'a']=tv; // ставим лист ts+1. Он соответствует переходу по c. t[ts][c]=ts+1;l[ts+1]=la;p[ts+1]=ts; // обновляем параметры текущей вершины. Не забыть про переход от предка tv к ts. l[tv]=tp;p[tv]=ts;t[p[ts]][a[l[ts]]-'a']=ts;ts+=2; // готовимся к спуску: поднялись на ребро и перешли по суффиксной ссылке. // tp будет отмечать, где мы в текущем суффиксе. tv=s[p[ts-2]];tp=l[ts-2]; // пока текущий суффикс не кончился, топаем вниз while (tp<=r[ts-2]) {tv=t[tv][a[tp]-'a'];tp+=r[tv]-l[tv]+1;} // если мы пришли в вершину, то поставим в нее суффиксную ссылку, иначе поставим в ts // (ведь на след. итерации мы создадим ts). if (tp==r[ts-2]+1) s[ts-2]=tv; else s[ts-2]=ts; // устанавливаем tp на новое ребро и идем добавлять букву к суффиксу. tp=r[tv]-(tp-r[ts-2])+2;goto suff; } }
void build() { ts=2; tv=0; tp=0; fill(r,r+N,(int)a.size()-1); // инициализируем данные для корня дерева s[0]=1; l[0]=-1; r[0]=-1; l[1]=-1; r[1]=-1; memset (t, -1, sizeof t); fill(t[1],t[1]+26,0); // добавляем текст в дерево по одной букве for (la=0; la<(int)a.size(); ++la) ukkadd (a[la]-'a'); } Перепиши на питоне.
- Assistant
N = 1000000 # максимальное число вершин в суффиксном дереве INF = 1000000000 # константа "бесконечность" a = "" # входная строка, для которой надо построить дерево t = [[-1] * 26 for _ in range(N)] # массив переходов (состояние, буква) l = [0] * N # левая r = [0] * N # и правая границы подстроки из a, отвечающие ребру, входящему в вершину p = [0] * N # предок вершины s = [0] * N # суффиксная ссылка tv = 0 # вершина текущего суффикса (если мы посередине ребра, то нижняя вершина ребра) tp = 0 # положение в строке соответствующее месту на ребре (от l[tv] до r[tv] включительно) ts = 0 # количество вершин la = 0 # текущий символ строки
def ukkadd(c): # дописать к дереву символ c global tv, tp, ts, la suff = True # будем приходить сюда после каждого перехода к суффиксу (и заново добавлять символ) while suff: if r[tv] < tp: # проверим, не вылезли ли мы за пределы текущего ребра # если вылезли, найдем следующее ребро. Если его нет - создадим лист и прицепим к дереву if t[tv][c] == -1: t[tv][c] = ts l[ts] = la p[ts] = tv ts += 1 tv = s[tv] tp = r[tv] + 1 continue tv = t[tv][c] # в противном случае просто перейдем к следующему ребру tp = l[tv]
if tp == -1 or c == ord(a[tp]) - ord('a'): # если буква на ребре совпадает с c то идем по ребру, а иначе # разделяем ребро на два. Посередине - вершина ts l[ts] = l[tv] r[ts] = tp-1 p[ts] = p[tv] t[ts][ord(a[tp]) - ord('a')] = tv # ставим лист ts+1. Он соответствует переходу по c. t[ts][c] = ts + 1 l[ts+1] = la p[ts+1] = ts # обновляем параметры текущей вершины. Не забыть про переход от предка tv к ts. l[tv] = tp p[tv] = ts t[p[ts]][ord(a[l[ts]]) - ord('a')] = ts ts += 2 # готовимся к спуску: поднялись на ребро и перешли по суффиксной ссылке. # tp будет отмечать, где мы в текущем суффиксе. tv = s[p[ts-2]] tp = l[ts-2] # пока текущий суффикс не кончился, топаем вниз while tp <= r[ts-2]: tv = t[tv][ord(a[tp]) - ord('a')] tp += r[tv] - l[tv] + 1 # если мы пришли в вершину, то поставим в нее суффиксную ссылку, иначе поставим в ts # (ведь на след. итерации мы создадим ts). if tp == r[ts-2] + 1: s[ts-2] = tv else: s[ts-2] = ts # устанавливаем tp на новое ребро и идем добавлять букву к суффиксу. tp = r[tv] - (tp - r[ts-2]) + 2 else: breakdef build(): global ts, tv, tp, la ts = 2 tv = 0 tp = 0 r[0] = -1 r[1] = -1 l[0] = -1 l[1] = -1 for _ in a: la = ord(_) - ord('a') ukkadd(la)
Пример использования:
a = "abacabadabacaba" build()