Skip to content

Instantly share code, notes, and snippets.

@mzsima
Created August 8, 2015 14:13
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save mzsima/a45e481de7a02f7cf0ce to your computer and use it in GitHub Desktop.
Save mzsima/a45e481de7a02f7cf0ce to your computer and use it in GitHub Desktop.
iOS C++ --- warshall floyd algorithm
#import "ViewController.h"
#include <vector>
#include <memory>
using namespace::std;
#define INF 9999999
class WarshallFloydSolver {
public:
void solve(int, int, int, int[][36]);
private:
void notify(int);
};
void WarshallFloydSolver::solve(int from, int to, int count, int cost[][36]) {
for (int k=0; k<count; k++)
for (int i=0; i<count; i++)
for (int j=0; j<count; j++)
cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);
notify(cost[from][to]);
}
void WarshallFloydSolver::notify(int i) {
[[NSNotificationCenter defaultCenter] postNotificationName:@"my message" object:@(i)];
}
@interface ViewController () {
int cost[36][36];
}
@property (nonatomic, weak) UIView *fromView;
@property (nonatomic, weak) UIView *toView;
@end
@implementation ViewController
- (void)viewDidLoad {
[super viewDidLoad];
self.view.backgroundColor = [UIColor lightGrayColor];
[self createMap];
[[NSNotificationCenter defaultCenter] addObserver:self selector:@selector(receiveMessage:) name:@"my message" object:nil];
}
- (void)createMap {
float d = 50;
// map
for (int i=0; i<36; i++) {
if ([self wallCheck:i]) {
continue;
}
float x = (i % 6) * d + 60;
float y = (i / 6) * d + 100;
UIView *box = [[UIView alloc] initWithFrame:CGRectMake(0, 0, d * 0.9, d * 0.9)];
box.tag = i + 1;
box.backgroundColor = [UIColor darkGrayColor];
box.layer.borderColor = [UIColor whiteColor].CGColor;
box.layer.borderWidth = 5;
box.center = CGPointMake(x, y);
[self.view addSubview:box];
}
// cost
for (int i=0; i<36; i++) {
for (int j=0; j<36; j++) {
cost[i][j] = INF;
if (i == j) {
cost[i][j] = 0;
} else if ((i % 6 == 0 && i == j + 1) || (i % 6 == 5 && i == j - 1)
|| [self wallCheck:i] || [self wallCheck:j]) {
cost[i][j] = INF;
} else if (i + 1 == j || i - 1 == j || i + 6 == j || i - 6 == j) {
cost[i][j] = 1;
}
}
}
}
- (BOOL)wallCheck:(int)i {
vector<int> walls = {3, 8 , 9, 15, 24};
return find(walls.begin(), walls.end(), i) != walls.end();
}
- (void)receiveMessage:(NSNotification *)note {
int tag = 12345;
[[self.view viewWithTag:tag] removeFromSuperview];
UILabel *distance = [[UILabel alloc] init];
distance.tag = tag;
distance.font = [UIFont boldSystemFontOfSize:80];
distance.text = [NSString stringWithFormat:@"%d", [note.object intValue]];
distance.textColor = [UIColor whiteColor];
[distance sizeToFit];
distance.center = CGPointMake(CGRectGetMidX(self.view.bounds), 450);
[self.view addSubview:distance];
}
- (void)touchesBegan:(NSSet *)touches withEvent:(UIEvent *)event {
CGPoint p = [[touches anyObject] locationInView:self.view];
UIView *v = [self.view hitTest:p withEvent:nil];
if (self.toView) {
self.toView.backgroundColor = [UIColor darkGrayColor];
self.fromView.backgroundColor = [UIColor darkGrayColor];
self.toView = nil;
self.fromView = nil;
}
if (v.tag > 0) {
if (self.fromView) {
self.toView = v;
v.backgroundColor = [UIColor greenColor];
shared_ptr<WarshallFloydSolver> cppClass(new WarshallFloydSolver());
cppClass->solve((int)self.fromView.tag - 1, (int)self.toView.tag - 1, 36, cost);
} else {
v.backgroundColor = [UIColor redColor];
self.fromView = v;
}
}
}
@end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment