Created
August 8, 2015 14:13
-
-
Save mzsima/a45e481de7a02f7cf0ce to your computer and use it in GitHub Desktop.
iOS C++ --- warshall floyd algorithm
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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