PavPS
BAN USER#include <iostream>
#include <assert.h>
#include <string>
#include <map>
#include <vector>
#include <set>
#include <queue>
using namespace std;
typedef struct
{
string src;
string dst;
string angle;
}Relation;
typedef struct RelationNode_{
string name;
map<string, set<RelationNode_*> > nodes;
}RelationNode;
RelationNode *findNodeByName(RelationNode * root, const string& name, const string& angle)
{
queue<RelationNode *> task;
task.push(root);
while (!task.empty())
{
if (task.front()->name == name)
return task.front();
for ( const auto& node : task.front()->nodes )
if (angle.empty() || node.first == angle)
for ( const auto& nodeInSet : node.second )
task.push(nodeInSet);
task.pop();
}
return nullptr;
}
string getOpposite(const string& angle)
{
if ("S" == angle) return "N"; else if ("N" == angle) return "S";
else if ("W" == angle) return "E"; else if ("E" == angle) return "W";
else if ("NE" == angle) return "SW"; else if ("SW" == angle) return "NE";
else if ("NW" == angle) return "SE"; else if ("SE" == angle) return "NW";
assert(false);
return string();
}
bool TryAddNode(RelationNode **root, const Relation& relation)
{
if (!*root)
{
*root = new RelationNode();
(*root)->name = relation.src;
}
const auto srcNode = findNodeByName(*root, relation.src, string());
if ( !srcNode )
// Sorry, for this task we do not create flat hierarchy. Only root-based
// It is easy to extend it by vector of roots.
return false;
const auto dstNode = findNodeByName(*root, relation.dst, string());
if ( dstNode )
// If we have this node already, we just make sure that is is correctly placed and test way back
return findNodeByName(srcNode, relation.dst, relation.angle)
||
findNodeByName(dstNode, relation.src, getOpposite(relation.angle));
const auto dst = new RelationNode();
dst->name = relation.dst;
if ( srcNode->nodes.end() == srcNode->nodes.find(relation.angle))
{
auto iter = srcNode->nodes.insert(make_pair(relation.angle, set<RelationNode_*>()));
iter.first->second.insert(dst);
}
else
{
srcNode->nodes[relation.angle].insert(dst);
}
return true;
}
bool isPossible(const vector<Relation>& pairs)
{
if (pairs.empty())
return true;
RelationNode *root = nullptr;
for (const auto& relation : pairs)
{
if (!TryAddNode(&root, relation))
return false;
}
return true;
}
void Google4()
{
Relation r1 { "p1", "p2", "SE" };
Relation r2 { "p2", "p3", "SE" };
Relation r3 { "p3", "p1", "SE" };
Relation r4 { "p3", "p1", "NW" };
assert( true == isPossible({ r1, r2 }) );
assert( false == isPossible({ r1, r2, r3 }) );
assert( true == isPossible({ r1, r2, r4 }) );
}
#include <iostream>
#include <algorithm>
#include <assert.h>
using namespace std;
typedef struct {
unsigned char r, g, b, a;
}ARGB;
typedef union {
ARGB color;
unsigned raw;
}PixelType;
static_assert( sizeof(unsigned) == 4 * sizeof(unsigned char), "type size is wrong" );
static const PixelType PixelWhite { {0xFF, 0xFF, 0xFF, 0xFF} };
const unsigned img_rgba_width = 16;
const unsigned img_rgba_height = 16;
const unsigned char img_rgba[] = {
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0xcc, 0xcc, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xfd, 0x5c, 0x5c, 0xff,
0xfd, 0x5c, 0x5c, 0xff, 0xfd, 0x5c, 0x5c, 0xff, 0xfd, 0x5c, 0x5c, 0xff,
0xfd, 0x5c, 0x5c, 0xff, 0xfd, 0x5c, 0x5c, 0xff, 0xfd, 0x5c, 0x5c, 0xff,
0xfd, 0x5c, 0x5c, 0xff, 0xfd, 0x5c, 0x5c, 0xff, 0xfd, 0x5c, 0x5c, 0xff,
0xfd, 0x5c, 0x5c, 0xff, 0xfd, 0x5c, 0x5c, 0xff, 0xfd, 0x5c, 0x5c, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0x72, 0x72, 0x72, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xfe, 0x43, 0x43, 0xff, 0xfe, 0x43, 0x43, 0xff, 0xfe, 0x43, 0x43, 0xff,
0xfe, 0x43, 0x43, 0xff, 0xfe, 0x43, 0x43, 0xff, 0xfe, 0x43, 0x43, 0xff,
0xfe, 0x43, 0x43, 0xff, 0xfe, 0x43, 0x43, 0xff, 0xfe, 0x43, 0x43, 0xff,
0xfe, 0x43, 0x43, 0xff, 0xfe, 0x43, 0x43, 0xff, 0xfe, 0x43, 0x43, 0xff,
0xfe, 0x43, 0x43, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0x75, 0x75, 0x75, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xf6, 0x40, 0x40, 0xff, 0xf6, 0x40, 0x40, 0xff,
0xf6, 0x40, 0x40, 0xff, 0xf6, 0x40, 0x40, 0xff, 0xf6, 0x40, 0x40, 0xff,
0xf6, 0x40, 0x40, 0xff, 0xf6, 0x40, 0x40, 0xff, 0xf6, 0x40, 0x40, 0xff,
0xf6, 0x40, 0x40, 0xff, 0xf6, 0x40, 0x40, 0xff, 0xf6, 0x40, 0x40, 0xff,
0xf6, 0x40, 0x40, 0xff, 0xf6, 0x40, 0x40, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0x75, 0x75, 0x75, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xf1, 0x3e, 0x3e, 0xff,
0xf1, 0x3e, 0x3e, 0xff, 0xf1, 0x3e, 0x3e, 0xff, 0xf1, 0x3e, 0x3e, 0xff,
0xf1, 0x3e, 0x3e, 0xff, 0xf1, 0x3e, 0x3e, 0xff, 0xf1, 0x3e, 0x3e, 0xff,
0xf1, 0x3e, 0x3e, 0xff, 0xf1, 0x3e, 0x3e, 0xff, 0xf1, 0x3e, 0x3e, 0xff,
0xf1, 0x3e, 0x3e, 0xff, 0xf1, 0x3e, 0x3e, 0xff, 0xf1, 0x3e, 0x3e, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0x75, 0x75, 0x75, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xea, 0x3c, 0x3c, 0xff, 0xea, 0x3c, 0x3c, 0xff, 0xff, 0xff, 0xff, 0xff,
0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xea, 0x3c, 0x3c, 0xff,
0xf9, 0x67, 0x67, 0xff, 0xea, 0x3c, 0x3c, 0xff, 0xea, 0x3c, 0x3c, 0xff,
0xea, 0x3c, 0x3c, 0xff, 0xf9, 0x67, 0x67, 0xff, 0xea, 0x3c, 0x3c, 0xff,
0xea, 0x3c, 0x3c, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0x75, 0x75, 0x75, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xe3, 0x39, 0x39, 0xff, 0xff, 0xff, 0xff, 0xff,
0xe3, 0x39, 0x39, 0xff, 0xe3, 0x39, 0x39, 0xff, 0xe3, 0x39, 0x39, 0xff,
0xe3, 0x39, 0x39, 0xff, 0xff, 0xff, 0xff, 0xff, 0xe3, 0x39, 0x39, 0xff,
0xe3, 0x39, 0x39, 0xff, 0xe3, 0x39, 0x39, 0xff, 0xff, 0xff, 0xff, 0xff,
0xe3, 0x39, 0x39, 0xff, 0xe3, 0x39, 0x39, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0x75, 0x75, 0x75, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xdb, 0x37, 0x37, 0xff,
0xff, 0xff, 0xff, 0xff, 0xdb, 0x37, 0x37, 0xff, 0xdb, 0x37, 0x37, 0xff,
0xf9, 0x67, 0x67, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
0xff, 0xff, 0xff, 0xff, 0xf9, 0x67, 0x67, 0xff, 0xff, 0xff, 0xff, 0xff,
0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xf9, 0x67, 0x67, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0x75, 0x75, 0x75, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xd2, 0x35, 0x35, 0xff, 0xff, 0xff, 0xff, 0xff, 0xd2, 0x35, 0x35, 0xff,
0xd2, 0x35, 0x35, 0xff, 0xd2, 0x35, 0x35, 0xff, 0xd2, 0x35, 0x35, 0xff,
0xff, 0xff, 0xff, 0xff, 0xd2, 0x35, 0x35, 0xff, 0xd2, 0x35, 0x35, 0xff,
0xd2, 0x35, 0x35, 0xff, 0xff, 0xff, 0xff, 0xff, 0xd2, 0x35, 0x35, 0xff,
0xd2, 0x35, 0x35, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0x75, 0x75, 0x75, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xff, 0xff, 0xff, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xf9, 0x67, 0x67, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xf9, 0x67, 0x67, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0x75, 0x75, 0x75, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xff, 0xff, 0xff, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0x75, 0x75, 0x75, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xff, 0xff, 0xff, 0xff,
0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0x75, 0x75, 0x75, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0x75, 0x75, 0x75, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0x75, 0x75, 0x75, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0x75, 0x75, 0x75, 0xff,
0xcc, 0xcc, 0xcc, 0xff, 0x75, 0x75, 0x75, 0xff, 0x75, 0x75, 0x75, 0xff,
0x75, 0x75, 0x75, 0xff, 0x75, 0x75, 0x75, 0xff, 0x75, 0x75, 0x75, 0xff,
0x75, 0x75, 0x75, 0xff, 0x75, 0x75, 0x75, 0xff, 0x75, 0x75, 0x75, 0xff,
0x75, 0x75, 0x75, 0xff, 0x75, 0x75, 0x75, 0xff, 0x75, 0x75, 0x75, 0xff,
0x75, 0x75, 0x75, 0xff, 0x75, 0x75, 0x75, 0xff, 0x75, 0x75, 0x75, 0xff,
0x75, 0x75, 0x75, 0xff
};
unsigned getPixelIndex(unsigned row, unsigned column, unsigned width)
{
return row * width + column;
}
PixelType const*generateImage(unsigned width, unsigned height)
{
return reinterpret_cast<PixelType const*>(img_rgba);
}
unsigned getPixelDifference(const PixelType& a, const PixelType& b)
{
const auto sum1 = a.color.r + a.color.g + a.color.b;
const auto sum2 = b.color.r + b.color.g + b.color.b;
return abs(sum1 - sum2);
}
PixelType *findEdges(unsigned width, unsigned height, PixelType const* original, unsigned threashold)
{
PixelType *result = new PixelType[ width * height];
for (unsigned r = 0; r < height; ++r)
for (unsigned c = 0; c < width; ++c)
{
const auto& pt = original[getPixelIndex(r, c, width)];
unsigned diff = 0;
if (c > 0) diff = max(diff, getPixelDifference(pt, original[getPixelIndex(r, c - 1, width)]) );
if (c < width-1) diff = max(diff, getPixelDifference(pt, original[getPixelIndex(r, c + 1, width)]) );
if (r > 0) diff = max(diff, getPixelDifference(pt, original[getPixelIndex(r - 1, c, width)]) );
if (r < height-1) diff = max(diff, getPixelDifference(pt, original[getPixelIndex(r + 1, c, width)]) );
if (diff > threashold)
result[getPixelIndex(r, c, width)].raw = PixelWhite.raw;
}
return result;
}
void displayEdgeImage(unsigned width, unsigned height, PixelType const* edges, bool (*predicate)(const PixelType& pixel))
{
for (unsigned r = 0; r < height; ++r)
{
for (unsigned c = 0; c < width; ++c)
if ( predicate(edges[getPixelIndex(r, c, width)]) )
cout << "* ";
else
cout << " ";
cout << endl;
}
}
void Epic3()
{
PixelType const*original = generateImage(img_rgba_width, img_rgba_height);
const auto lambda = [](const PixelType& pixel)->bool {return pixel.color.r > 200 && pixel.color.g > 200 && pixel.color.b > 200;};
displayEdgeImage(img_rgba_width, img_rgba_height, original, lambda);
PixelType *edges = findEdges(img_rgba_width, img_rgba_height, original, 200);
displayEdgeImage(img_rgba_width, img_rgba_height, edges, lambda);
}
#if !defined(_MSC_VER)
int main()
{
Epic3();
return 0;
}
#endif
- PavPS January 29, 2015