Подсчет комнат, зная, где стены
Этот вопрос касается кода для C++ builder 6. Баунти заинтересован в стандартном алгоритме C++ для решения проблемы с учетом стандартизированного ввода (см. Это для получения дополнительной информации.)
TXT-файл, который также представляет данные, которые я имею в массиве:
1101 0110 1101 0110 1100 0101 0110
1110 1001 0110 1011 1010 1111 1010
1000 0101 0011 1110 1011 1110 1010
1011 1101 0101 0001 0101 0011 1011
Объяснение текста:
Числа из txt файла представляют собой 4-битное представление стен комнаты, а установленный бит представляет стену. Стенные биты расположены по часовой стрелке, начиная с самого значительного бита, являющегося западной стеной. Например, 1101 представляет комнату, где:
- The set bit in the most significant position indicates a wall to the West
- The set bit in the next most significant position indicates a wall to the North
- Неустановленный бит указывает на отсутствие стены на востоке
- The set bit in the least significant position indicates a wall to the South
Дано:
- Наружные стены комнат всегда будут иметь стену
- Внутренние стены всегда будут выражены в обеих комнатах (в примере, поскольку комната в (1, 1) равна 1101, она содержит стену на юг, комната в (1, 2) 1110 должна содержать стену на север
- Там никогда не будет больше, чем
numeric_limits<int>::max()номера
Меня попросили опубликовать мой код, вот он:
Я пытался решить эту проблему, но я получаю EAAccessviolation может кто-нибудь сказать мне, что я делаю неправильно?
int rn=0,z=0, global=0,coord[15],c[411],b1[411];
void peruse ( int i, int j,int* bb)
{
bool top=false,bottom=false,right=false,left=false;
//truth checks
if (bb[i*m+j]<1000) left=true;
if (bb[i*m+j]<100) top=true; else if (bb[i*m+j]-1000<100) top=true;
if (bb[i*m+j]<10) right=true; else
if ( (bb[i*m+j]-100<10) || (bb[i*m+j]-1000<10) || (bb[i*m+j]-100<10) ) right=true;
if (bb[i*m+j]<1) bottom=true; else
if ( (bb[i*m+j]-10<1) || (bb[i*m+j]-100<1) || (bb[i*m+j]-1000<1) ||(bb[i*m+j]-100<1))
bottom=true;
//marc
if (left)
{
c[i*m+j]=c[i*m+j]+1000; // EAaccessViolation i dont know why.....
peruse(i,j-1,c);
}
if (top)
{
c[i*m+j]=c[i*m+j]+100;
peruse(i-1,j,c);
}
if (right)
{
c[i*m+j]=c[i*m+j]+10;
peruse(i,j+1,c);
}
if (bottom)
{
c[i*m+j]=c[i*m+j]+1;
peruse(i+1,i,c);
}
if ( !(left) && !(top) && !(right) && !(bottom) )
{
bb[411]++;
}
}
void __fastcall TForm1::Button7Click(TObject *Sender)
{
b1[411]=0;
for(int i=0;i<n;i++)
for (int j=0;j<m;j++)
{
b1[i*m+j]=b[i][j];
c[i*m+j]=b[i][j];
}
peruse (1,1,b1);
ShowMessage("Nr. "+IntToStr(b1[411]) );
}
5 ответов
Это типичная проблема определения общего числа связанных компонентов в графе.
Позвольте мне помочь вам визуализировать аналогию, сосредоточив внимание на следующих моментах, имея в виду, что здесь мы имеем дело с неориентированными графами.
1. В графе мы имеем различные вершины, и две вершины называются смежными, если между ними есть ребро. Точно так же, как ваш замок, где две ячейки примыкают друг к другу, если одна ячейка может привести к другой ячейке.
2 В графе две вершины принадлежат одному и тому же связному компоненту, если существует путь между двумя вершинами с использованием ребер. Точно так же, как ваш замок, где две ячейки принадлежат одному и тому же номеру комнаты, если одна клетка, следуя пути ячеек, может привести к другой.
3 В графе мы связали компоненты, так что связная компонента составлена из вершин, так что каждые две вершины связной компоненты имеют путь между ними.Точно так же, как в вашем замке, где у нас есть комнаты, так что каждые две клетки одной комнаты имеют путь между клетками.
Теперь, если вам все еще интересно, как построить график, это легко.
Количество вершин будет NxM(для замка размером N строк и M столбцов), который равен числу ячеек.
Просто пронумеруйте ячейки последовательно и между cell a(meaning vertex a) а также cell b(vertex b) если обе клетки соседние
Теперь общее количество комнат можно легко подсчитать, применив алгоритм bfs или dfs к построенному вами графику.
Алгоритм описан в первой ссылке, которую я предоставил.
Честно говоря, я просто очень хотел попытаться решить это. Поэтому я хочу сказать, что вы приложили смелые усилия для этого и просто пошли дальше и покажем вам, как это сделать. Я предполагаю, что вы можете указать следующий алгоритм:
- Входные числа считываются в двоичном виде (поэтому "1101" будет читаться как десятичное число "13")
- Все эти цифры в
const vector<char> rooms - Ширина каждого ряда "комнат" может быть помещена в
size_t width(который должен быть одинаковым во всех рядах, мы должны работать с прямоугольником комнат) - Все внешние "стены" "комнат" будут иметь "стену"
- Есть меньше чем
numeric_limits<int>::max()"номера"
Мы будем использовать vector<int> temp чтобы обозначить каждую комнату, мы построим ее размером rooms и инициализировать каждую метку в 0. int result будет использоваться для маркировки комнат и будет инициализироваться до 0. Но поскольку все метки комнат не будут уменьшаться при замене метки меньшего размера, size(set<int>(cbegin(temp), cend(temp))) будет использоваться для определения окончательного количества меток.
Наше решение будет построено вокруг функции, занимающей 2 "комнаты", между которыми нет стены; такой что либо:
- Одна комната еще не помечена, и в этом случае она будет иметь метку другой комнаты
- Обе комнаты имеют общий ярлык, и в этом случае никаких действий не будет
- Ярлык на одну комнату меньше, и в этом случае всем комнатам с большей меткой будет присвоен меньший номер
Важное замечание об этой функции, я использую унарный оператор плюс для создания R-значения int из L-значений int& больше информации здесь. Более ясное решение, вероятно, будет использовать static_cast<int> но по какой-то причине Visual Studio 2015 не работает, как ожидалось, больше информации здесь.
void generate(vector<int>& temp, int& target, const size_t width, const size_t i) {
const auto replacement = temp[i];
if (target > replacement) {
replace(begin(temp), next(begin(temp), min(size(temp), i + width - 1)), target, replacement);
} else {
target = replacement;
}
}
Используя этот код, мы можем:
for (size_t i = 0U; i < size(rooms); ++i) {
const auto toWest = (rooms[i] & 0b1000) == 0;
const auto toNorth = (rooms[i] & 0b100) == 0;
const auto toEast = (rooms[i] & 0b10) == 0;
const auto toSouth = (rooms[i] & 0b1) == 0;
const auto west = toWest && temp[i - 1] != 0 ? temp[i - 1] : numeric_limits<int>::max();
const auto north = toNorth && temp[i - width] != 0 ? temp[i - width] : numeric_limits<int>::max();
const auto east = toEast && temp[i + 1] != 0 ? temp[i + 1] : numeric_limits<int>::max();
temp[i] = min({ temp[i] != 0 ? temp[i] : numeric_limits<int>::max(), result + 1, west, north, east });
if (temp[i] == result + 1) ++result;
if (toWest) generate(temp, temp[i - 1], width, i);
if (toNorth) generate(temp, temp[i - width], width, i);
if (toEast) generate(temp, temp[i + 1], width, i);
if (toSouth) temp[i + width] = temp[i];
}
Есть несколько проблем с вашим кодом, которые запрещают правильную отладку с третьей стороны, например, недостаточно информации о том, как это работает, неопределенные переменные (m,n,b) переполнение массива (многочисленный доступ к [411] пока размер только 411 вместо 412) отговаривать любого даже начинать пробовать (заставляя задуматься, действительно ли код полезен и стоит ли тратить время). Мне также было любопытно, так что здесь моя простая неоптимизированная попытка в BDS2006 Turbo C++ (преемник BCB6, так что этот код должен работать там же) для этой задачи.
[rooms.h]
//---------------------------------------------------------------------------
#ifndef _rooms_h
#define _rooms_h
//---------------------------------------------------------------------------
class rooms
{
public:
// variables
int xs,ys; // map resolution
DWORD **map; // map[xs][ys]
enum
{
_W=8,
_N=4,
_E=2,
_S=1
};
// internals
rooms();
~rooms();
void _free(); // release map memory
// inteface
void resize(int _xs,int _ys); // realloc map to new resolution
void set(AnsiString txt); // copy txt to map
void draw(TCanvas *scr,int x,int y,int sz); // draw map on Canvas at (x,y) with grid size sz
int count(); // count rooms
};
//---------------------------------------------------------------------------
rooms::rooms() { map=NULL; xs=0; ys=0; }
rooms::~rooms() { _free(); }
//---------------------------------------------------------------------------
void rooms::_free()
{
if (map)
{
for (int x=0;x<xs;x++)
if (map[x])
delete[] map[x];
delete[] map;
}
map=NULL; xs=0; ys=0;
}
//---------------------------------------------------------------------------
void rooms::resize(int _xs,int _ys)
{
if ((xs==_xs)&&(ys==_ys)) return;
_free();
xs=_xs; ys=_ys;
map=new DWORD*[xs];
for (int x=0;x<xs;x++)
map[x]=new DWORD[ys];
}
//---------------------------------------------------------------------------
void rooms::set(AnsiString txt)
{
int i,l,x,y,n0,n1;
l=txt.Length(); if (!l) return;
// count eof lines (ys)
for (y=0,i=1;i<=l;i++)
if ((txt[i]==13)||(txt[i]==10))
{
y++;
if (i<l)
if ((txt[i+1]==13)||(txt[i+1]==10)) i++;
}
if ((txt[l]!=13)&&(txt[l]!=10)) y++; // handle missing last eof
// count numbers per line (xs)
for (n1=0,x=0,i=1;i<=l;i++)
{
n0=n1; n1=0;
if ((txt[i]=='0')||(txt[i]=='1')) n1=1;
if ((txt[i+1]==13)||(txt[i+1]==10)) break;
if ((!n0)&&(n1)) x++;
}
// copy data
resize(x,y);
for (x=0,y=0,i=1;i<=l;)
{
// skip spaces
while ((i<=l)&&(txt[i]!='0')&&(txt[i]!='1')) i++;
// read 4 bit bin number
n0= 0; if (i>l) break; if (txt[i]=='1') n0|=1; i++;
n0<<=1; if (i>l) break; if (txt[i]=='1') n0|=1; i++;
n0<<=1; if (i>l) break; if (txt[i]=='1') n0|=1; i++;
n0<<=1; if (i>l) break; if (txt[i]=='1') n0|=1; i++;
map[x][y]=n0;
x++; if (x>=xs) { x=0; y++; if (y>=ys) break; }
}
// clear the rest in case of error in data
if ((y<ys)&&(x<xs)) for (;;)
{
map[x][y]=0;
x++; if (x>=xs) { x=0; y++; if (y>=ys) break; }
}
}
//---------------------------------------------------------------------------
void rooms::draw(TCanvas *scr,int x0,int y0,int sz)
{
int x,y,xx,yy;
DWORD a;
scr->Brush->Color=clDkGray;
scr->Brush->Style=bsSolid;
scr->FillRect(Rect(x0,y0,x0+xs*sz,y0+ys*sz));
scr->Pen->Color=clBlue;
scr->Pen->Width=5;
scr->Font->Color=clBlack;
scr->Brush->Style=bsClear;
for (xx=x0,x=0;x<xs;x++,xx+=sz)
for (yy=y0,y=0;y<ys;y++,yy+=sz)
{
a=map[x][y]&15;
if (DWORD(a&_W)) { scr->MoveTo(xx ,yy ); scr->LineTo(xx ,yy+sz); }
if (DWORD(a&_N)) { scr->MoveTo(xx ,yy ); scr->LineTo(xx+sz,yy ); }
if (DWORD(a&_E)) { scr->MoveTo(xx+sz,yy ); scr->LineTo(xx+sz,yy+sz); }
if (DWORD(a&_S)) { scr->MoveTo(xx ,yy+sz); scr->LineTo(xx+sz,yy+sz); }
scr->TextOutA(xx+(sz>>1),yy+(sz>>1),map[x][y]>>4);
}
scr->Brush->Style=bsSolid;
scr->Pen->Width=1;
}
//---------------------------------------------------------------------------
int rooms::count()
{
int x,y,i,i0,i1,w0,w1,n,e;
// each block is a separate room
for (n=0,x=0;x<xs;x++)
for (y=0;y<ys;y++,n+=16)
{
map[x][y]&= 0x0000000F; // low 4 bits are walls
map[x][y]|=n&0xFFFFFFF0; // rest is room index
} n>>=4;
// reindex all indexes i0 to i1
#define map_reindex(i0,i1) \
for (x=0;x<xs;x++) \
for (y=0;y<ys;y++) \
if (DWORD(map[x][y]&0xFFFFFFF0)==i0) \
{ \
map[x][y]&= 0x0000000F; \
map[x][y]|=i1&0xFFFFFFF0; \
}
// loop until no change has occured
for (e=1;e;)
{
e=0;
// merge columns
for (x=0;x<xs;x++)
for (y=1;y<ys;y++)
{
w0=map[x][y-1]&0x0000000F;
i0=map[x][y-1]&0xFFFFFFF0;
w1=map[x][y ]&0x0000000F;
i1=map[x][y ]&0xFFFFFFF0;
if ((i0!=i1)&&(DWORD(w0&_S)==0)&&(DWORD(w1&_N)==0)) { map_reindex(i0,i1); n--; e=1; }
}
// merge rows
for (y=0;y<ys;y++)
for (x=1;x<xs;x++)
{
w0=map[x-1][y]&0x0000000F;
i0=map[x-1][y]&0xFFFFFFF0;
w1=map[x ][y]&0x0000000F;
i1=map[x ][y]&0xFFFFFFF0;
if ((i0!=i1)&&(DWORD(w0&_E)==0)&&(DWORD(w1&_W)==0)) { map_reindex(i0,i1); n--; e=1; }
}
}
return n;
#undef map_reindex
}
//---------------------------------------------------------------------------
#endif
//---------------------------------------------------------------------------
[И источник окна C++ приложения VCL в одном окне без какого-либо компонента]
//$$---- Form CPP ----
//---------------------------------------------------------------------------
#include <vcl.h>
#pragma hdrstop
#include "Unit1.h"
#include "rooms.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
Graphics::TBitmap *bmp; // back buffer
int xs,ys; // actual window resolution
rooms map; // map of rooms
//---------------------------------------------------------------------------
void draw()
{
int x,y,sz;
// clear bachground
bmp->Canvas->Brush->Color=clBlack;
bmp->Canvas->Brush->Style=bsSolid;
bmp->Canvas->FillRect(Rect(0,0,xs,ys));
// compute grid size
x=(xs-20)/map.xs; sz=x;
y=(ys-20)/map.ys; if (x>y) sz=y;
// and map position so it is centered
x=(xs-(sz*map.xs))>>1;
y=(ys-(sz*map.ys))>>1;
// render to backbuffer (avoid flickering)
map.draw(bmp->Canvas,x,y,sz);
// render backbuffer to window
Form1->Canvas->Draw(0,0,bmp);
}
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner):TForm(Owner)
{
// init backbuffer
bmp=new Graphics::TBitmap;
bmp->HandleType=bmDIB;
bmp->PixelFormat=pf32bit;
// init map
map.set("1101 0110 1101 0110 1100 0101 0110\r\n1110 1001 0110 1011 1010 1111 1010\r\n1000 0101 0011 1110 1011 1110 1010\r\n1011 1101 0101 0001 0101 0011 1011\r\n");
Caption=map.count(); // result count is in the Window Caption
}
//---------------------------------------------------------------------------
void __fastcall TForm1::FormDestroy(TObject *Sender) { delete bmp; }
//---------------------------------------------------------------------------
void __fastcall TForm1::FormPaint(TObject *Sender) { draw(); }
//---------------------------------------------------------------------------
void __fastcall TForm1::FormResize(TObject *Sender)
{
// get actual window size
xs=ClientWidth;
ys=ClientHeight;
// resize backbufer and force redraw
bmp->SetSize(xs,ys);
draw();
}
//---------------------------------------------------------------------------
Идея моего решателя для этого проста:
IDкаждая ячейка сетки по отдельному номеру комнатызапомнить количество клеток как
nобъединить все соседние комнаты без стен между ними
так что проходите по всем комнатам, и если в любой соседней камере нет стены, и есть другая комната
IDпереиндексируйте номер комнаты, чтобы в комнатах кабинета был такой же номер. Также уменьшить счетчик номераn,цикл № 2, пока не происходит переиндексация
[Заметки]
Не забудьте создать соответствующие события в вашей среде IDE вместо простого копирования кода, иначе он не будет работать.
Одним простым способом было бы создать массив с размером комнаты и инициализировать его "0". После этого вы должны перебрать массив. Если вы найдете "0", вы начнете BFS с этой точки и раскрасите результаты массива до текущего числа.
Информация о БФС
BFS должен посмотреть на прямого соседа и проверить, есть ли в этом массиве "0". Если это правда, BFS должен проверить, нет ли стены между двумя полями. Если между ними нет стены, закрасьте это поле текущим цветом (в начале 1) и вызовите BFS на новом поле.
BFS останавливается автоматически, когда комната полностью окрашена. тогда глобальный цвет будет увеличен на 1, и цикл продолжается и ищет следующий "0".
После цикла количество комнат сохраняется в глобальном значении цвета.
этот алгоритм работает в O(N)
Небольшой пример:
//CountingRooms.h
#include <vector>
class CountingRooms
{
public:
CountingRooms();
~CountingRooms();
int Count();
void TestFill();
void Print();
private:
struct Point
{
int x = 0;
int y = 0;
};
unsigned int* m_arrFieldColors = nullptr;
unsigned int* m_arrFieldWalls = nullptr;
int m_nSizeX = 0;
int m_nSizeY = 0;
int m_nCurrentColor = 0;
unsigned int GetValue(unsigned int* field, int x, int y);
void SetValue(unsigned int* field, int x, int y, unsigned int value);
bool CanPass(int x1, int y1, int x2, int y2);
void DFS(int posX, int posY);
bool IsInsideArray(int x1, int y1);
};
//CountingRooms.cpp
#include "stdafx.h"
#include "CountingRooms.h"
#include <iostream>
CountingRooms::CountingRooms()
{
}
CountingRooms::~CountingRooms()
{
if (m_arrFieldColors)
{
delete[]m_arrFieldColors;
}
if (m_arrFieldWalls)
{
delete[]m_arrFieldWalls;
}
}
bool CountingRooms::IsInsideArray(int x, int y)
{
return x >= 0 && y >= 0 && x < m_nSizeX && y < m_nSizeY;
}
bool CountingRooms::CanPass(int x1, int y1, int x2, int y2)
{
if (IsInsideArray(x1, y1) && IsInsideArray(x2, y2)) //inside the array range
{
if (x2 - x1 == 1 && y2 - y1 == 0) // right
{
if (!(GetValue(m_arrFieldWalls, x1, y1) & 2) && !(GetValue(m_arrFieldWalls, x2, y2) & 8)) { return true; }
}
if (x2 - x1 == 0 && y2 - y1 == -1) // up
{
if (!(GetValue(m_arrFieldWalls, x1, y1) & 4) && !(GetValue(m_arrFieldWalls, x2, y2) & 1)) { return true; }
}
if (x2 - x1 == -1 && y2 - y1 == 0) // left
{
if (!(GetValue(m_arrFieldWalls, x1, y1) & 8) && !(GetValue(m_arrFieldWalls, x2, y2) & 2)) { return true; }
}
if (x2 - x1 == 0 && y2 - y1 == 1) // down
{
if (!(GetValue(m_arrFieldWalls, x1, y1) & 1) && !(GetValue(m_arrFieldWalls, x2, y2) & 4)) { return true; }
}
}
return false;
}
void CountingRooms::DFS(int posX, int posY)
{
if (GetValue(m_arrFieldColors, posX, posY)) // check if the field is already colored
{
return;
}
Point sStart;
sStart.x = posX;
sStart.y = posY;
std::vector<Point> vecList;
vecList.push_back(sStart);
m_nCurrentColor++;
while (vecList.size()) // as long as something is inside the list
{
Point sTemp = vecList[vecList.size()-1]; //get out the last element
vecList.pop_back();
if (IsInsideArray(sTemp.x, sTemp.y))
{
if (!GetValue(m_arrFieldColors, sTemp.x, sTemp.y)) // is field not colored
{
SetValue(m_arrFieldColors, sTemp.x, sTemp.y, m_nCurrentColor);
if (CanPass(sTemp.x, sTemp.y, sTemp.x + 1, sTemp.y)) /* right*/
{
Point newPoint;
newPoint.x = sTemp.x + 1;
newPoint.y = sTemp.y;
vecList.push_back(newPoint);
}
if (CanPass(sTemp.x, sTemp.y, sTemp.x - 1, sTemp.y)) /* left*/
{
Point newPoint;
newPoint.x = sTemp.x - 1;
newPoint.y = sTemp.y;
vecList.push_back(newPoint);
}
if (CanPass(sTemp.x, sTemp.y, sTemp.x, sTemp.y - 1)) /* up*/
{
Point newPoint;
newPoint.x = sTemp.x;
newPoint.y = sTemp.y - 1;
vecList.push_back(newPoint);
}
if (CanPass(sTemp.x, sTemp.y, sTemp.x, sTemp.y + 1)) /* down*/
{
Point newPoint;
newPoint.x = sTemp.x;
newPoint.y = sTemp.y + 1;
vecList.push_back(newPoint);
}
}
}
}
}
int CountingRooms::Count()
{
m_nCurrentColor = 0;
for (int i = 0; i < m_nSizeY; ++i)
{
for (int j = 0; j < m_nSizeX; ++j)
{
DFS(j, i);
}
}
return m_nCurrentColor;
}
void CountingRooms::TestFill()
{
m_arrFieldWalls = new unsigned int[42]{13, 6,13, 6,12, 5, 6,
14, 9, 6,11,10,15,10,
8, 5, 3,14,11,14,10,
11,13, 5, 1, 5, 3,11};
m_arrFieldColors = new unsigned int[42];
for (int i = 0; i < 42;i++)
{
m_arrFieldColors[i] = 0;
}
m_nSizeX = 7;
m_nSizeY = 4;
}
unsigned int CountingRooms::GetValue(unsigned int* field, int x, int y)
{
if (IsInsideArray(x, y))
{
return field[x + m_nSizeX*y];
}
return -1;
}
void CountingRooms::SetValue(unsigned int* field, int x, int y, unsigned int value)
{
if (IsInsideArray(x, y))
{
field[x + m_nSizeX*y] = value;
}
}
void CountingRooms::Print()
{
std::cout << "Walls:" << std::endl;
for (int j = 0; j < m_nSizeY;++j)
{
for (int i = 0; i < m_nSizeX;++i)
{
std::cout << GetValue(m_arrFieldWalls, i, j) << "\t";
}
std::cout << std::endl;
}
std::cout << std::endl<<"Colors:" << std::endl;
for (int j = 0; j < m_nSizeY;++j)
{
for (int i = 0; i < m_nSizeX;++i)
{
std::cout << GetValue(m_arrFieldColors, i, j) << "\t";
}
std::cout << std::endl;
}
}
//main.cpp
#include "stdafx.h"
#include <iostream>
#include "CountingRooms.h"
int main()
{
CountingRooms cr;
cr.TestFill();
std::cout<<"There are "<<cr.Count()<<" rooms"<<std::endl;
cr.Print();
char key = 0;
std::cin >> key;
return 0;
}
Кстати: BFS заменяется DFS, но оба работают.
Выход
Непересекающиеся множества вместе с Union-Find хорошо подходят для задач связанных компонентов. Вместо графика я отслеживаю различные непересекающиеся наборы плиток для пола. Каждый набор имеет собственную репрезентативную плитку, которая однозначно идентифицирует набор.
Вы можете прочитать больше о Union-Find здесь.
Алгоритм прост:
Для каждой плитки обработайте соседние плитки, если общая стена отсутствует. Это делается с помощью простого
union()из двух плиток. Когда мы закончим, каждая плитка будет принадлежать одному из непересекающихся наборов (каждый набор представляет связанное пространство или комнату). В прикрепленном кодеparent[]хранит представительный элемент.- Когда закончите, нормализуйте репрезентативный элемент каждой плитки.
Подсчитайте количество уникальных репрезентативных элементов. Это количество непересекающихся множеств (и, следовательно, количество связанных пространств или комнат).
Некоторые дополнительные наблюдения:
В любое время вам нужно только обработать северную и западную стены. (Почему? Доказательство оставлено читателю.)
Это потому что для плитки
a[i][j]его южные и восточные стены могут быть обработаны плиткойa[i+1][j]а такжеa[i][j+1]соответственно.Почему нам нужно нормализовать представителя каждой плитки? Причина в том, что некоторые наборы могут заканчиваться двумя или более репрезентативными элементами. Мы рекурсивно находим родительский элемент, чтобы получить уникального представителя для всего набора. (Если вы хотите проверить это, закомментируйте следующую строку из прикрепленного кода:
// normalise each tile parent[i] = findSet(parent[i]);Прикрепленный код использует специальную версию Union-Find с двумя эвристиками:
- Союз по рангу (что подтверждается
ranks[]) - Сжатие пути
- Союз по рангу (что подтверждается
Прикрепленный код: живой пример