UnionFindで迷路的なものを作るiPhoneアプリ(C++)のサンプルコードを書いてみます。
#import “ViewController.h”
#include <vector>
#include <memory>
using namespace std;
// reference -> http://www.prefield.com/algorithm/container/union_find.html
typedef struct UnionFind {
vector<int> data;
void reset(int size) {
for (int i=0; i<25; i++) data.push_back(-1);
}
bool unite(int x, int y) {
x = root(x); y = root(y);
if (x != y) {
if (data[y] < data[x]) swap(x, y);
data[x] += data[y]; data[y] = x;
}
return x != y;
}
bool findSet(int x, int y) {
return root(x) == root(y);
}
int root(int x) {
return data[x] < 0 ? x : data[x] = root(data[x]);
}
int size(int x) {
return –data[root(x)];
}
} UnionFind;
@interface ViewController () {
UnionFind uf;
}
@end
@implementation ViewController
– (void)viewDidLoad {
[super viewDidLoad];
[self setupUF];
[self createWall];
}
– (void)setupUF {
uf.reset(25);
}
– (void)createWall {
int rcnt = 5;
for (int i=0; i<rcnt * rcnt; i++) {
int row = (i / rcnt);
int col = (i % rcnt);
//panel
UIView *panel = [[UIView alloc] initWithFrame:CGRectMake(col * 50 + 50, row * 50 + 50, 50, 50)];
panel.tag = i + 1;
panel.backgroundColor = [UIColor yellowColor];
[self.view addSubview:panel];
// top
{
CALayer *wall = [CALayer layer];
if (row > 0) {
wall.name = [NSString stringWithFormat:@”%d %d”, i , i -rcnt];
}
wall.frame = CGRectMake(col * 50 + 50, row * 50 + 50, 50, 2);
wall.backgroundColor = [UIColor blackColor].CGColor;
[self.view.layer addSublayer:wall];
}
// left
{
CALayer *wall = [CALayer layer];
if (col > 0) {
wall.name = [NSString stringWithFormat:@”%d %d”, i – 1 , i];
}
wall.frame = CGRectMake(col * 50 + 50, row * 50 + 50, 2, 50);
wall.backgroundColor = [UIColor blackColor].CGColor;
[self.view.layer addSublayer:wall];
}
// right
if (col == rcnt – 1) {
CALayer *wall = [CALayer layer];
wall.frame = CGRectMake(col * 50 + 100, row * 50 + 50, 2, 50);
wall.backgroundColor = [UIColor blackColor].CGColor;
[self.view.layer addSublayer:wall];
}
// bottom
if (row == rcnt – 1) {
CALayer *wall = [CALayer layer];
wall.frame = CGRectMake(col * 50 + 50, row * 50 + 100, 50, 2);
wall.backgroundColor = [UIColor blackColor].CGColor;
[self.view.layer addSublayer:wall];
}
}
}
– (void)touchesBegan:(NSSet *)touches withEvent:(UIEvent *)event
{
[self randomWallAndCheck];
}
– (void)randomWallAndCheck {
NSArray *walls = [self.view.layer.sublayers filteredArrayUsingPredicate:[NSPredicate predicateWithFormat:@”name != nil”]];
NSUInteger random = (NSUInteger)arc4random % walls.count;
CALayer *targetWall = walls[random];
NSArray *nums = [targetWall.name componentsSeparatedByString:@” “];
uf.unite([nums[0] intValue], [nums[1] intValue]);
[targetWall removeFromSuperlayer];
// check
for (int i=0; i<25; i++) {
UIView *panel = [self.view viewWithTag:i + 1];
int colorNumber = uf.root(i);
panel.backgroundColor = [UIColor colorWithHue:colorNumber * 0.025 saturation:0.5 brightness:1 alpha:1];
}
}
@end