Depth First Searchで水たまりの数を数えるiPhoneアプリ(C++)のサンプルコードを描いてみます。
#import “ViewController.h”
#include <memory>
using namespace std;
#define MAX_N 10
#define MAX_M 10
class LakeCounter {
public:
char field[MAX_N][MAX_M + 1];
int result;
void setupField();
void solve();
private:
void dfs(int, int);
void notify(int, int);
};
void LakeCounter::setupField() {
for (int i=0; i < MAX_N; i++) {
for (int j=0; j < MAX_M; j++) {
field[i][j] = (arc4random() % 6) > 2 ? ‘.’ : ‘W’;
}
}
}
void LakeCounter::solve() {
result = 0;
for (int i=0; i<MAX_N; i++) {
for (int j=0; j<MAX_M; j++) {
if (field[i][j] == ‘W’) {
dfs(i, j);
result++;
}
}
}
}
void LakeCounter::dfs(int x, int y) {
notify(x, y); // message to view controller
field[x][y] = ‘.’;
// 8 direction
for (int dx = –1; dx <= 1; dx++) {
for (int dy = –1; dy <= 1; dy++) {
int nx = x + dx, ny = y + dy;
if (0 <= nx && nx < MAX_N && 0 <= ny && ny < MAX_M && field[nx][ny] == ‘W’) {
dfs(nx, ny);
}
}
}
return;
}
void LakeCounter::notify(int x, int y) {
[[NSNotificationCenter defaultCenter] postNotificationName:@”mymessage” object:@[@(result), @(x), @(y)]];
}
@interface ViewController ()
@end
@implementation ViewController
– (void)viewDidLoad {
[super viewDidLoad];
self.view.backgroundColor = [UIColor colorWithHue:0.25 saturation:0.1 brightness:1 alpha:1];
self.view.tag = HUGE_VAL;
[self setup];
}
– (void)setup {
shared_ptr<LakeCounter> cppClass(new LakeCounter());
cppClass->setupField();
for (int i=0; i < MAX_N; i++) {
for (int j=0; j < MAX_M; j++) {
UIView *panel = [[UIView alloc] initWithFrame:CGRectMake(0, 0, 30, 30)];
int ii = (i+1) << 5;
panel.tag = ii + j + 1; // max 2^5
panel.center = CGPointMake(i * 30 + 50, j * 30 + 80);
panel.backgroundColor = (cppClass->field[i][j] == ‘W’) ? [UIColor blueColor] : [UIColor greenColor];
[self.view addSubview:panel];
}
}
[[NSNotificationCenter defaultCenter] addObserver:self selector:@selector(receiveMessage:) name:@”mymessage” object:nil];
cppClass->solve();
}
– (void)receiveMessage:(NSNotification *)note {
int result = [note.object[0] intValue];
int x = ([note.object[1] intValue] + 1) << 5;
int y = [note.object[2] intValue] + 1;
UIView *v = [self.view viewWithTag:x + y];
[UIView animateWithDuration:1 animations:^{
v.layer.transform = CATransform3DMakeRotation(M_PI * 0.5, 1, 0, 0);
} completion:^(BOOL finished) {
v.backgroundColor = [UIColor colorWithHue: 0.4 + result * 0.1 saturation:0.4 brightness:1 alpha:1];
[UIView animateWithDuration:1 animations:^{
v.layer.transform = CATransform3DMakeRotation(M_PI, 1, 0, 0);
}];
}];
}
– (void)touchesBegan:(NSSet *)touches withEvent:(UIEvent *)event
{
[self.view.subviews enumerateObjectsUsingBlock:^(UIView *v, NSUInteger idx, BOOL *stop) {
[v removeFromSuperview];
}];
[self setup];
}
@end