#include <iostream>
#include <iostream>
#include <fstream>
using namespace std;
#define UP(i, j) flowInput(((i - 1) * n + j) * 2, ((i - 2) * n + j) * 2 - 1, 1); // 위와 연결
#define DOWN(i, j) flowInput(((i - 1) * n + j) * 2, (i * n + j) * 2 - 1, 1); // 아래와 연결
#define LEFT(i, j) flowInput(((i - 1) * n + j) * 2, ((i - 1) * n + (j - 1)) * 2 - 1, 1); // 왼쪽과 연결
#define RIGHT(i, j) flowInput(((i - 1) * n + j) * 2, ((i - 1) * n + (j + 1)) * 2 - 1, 1); // 오른쪽과 연결
int v, e;
struct Link
{
Link(int u, int capacity)
{
this->u = u;
this->flow = 0;
this->capacity = capacity;
this->cosine = NULL;
next = NULL;
}
int u;
int capacity;
int flow;
Link *cosine;
Link *next;
};
#include<iostream>
using namespace std;
template<typename T>
struct Node{
T data;
Node* next;
Node(T d, Node* n = NULL) : data(d), next(n){}
};
struct Item
{
int u;
int localResidue;
Item *next;
};
Link **graph;
int *seen;
int *parent;
//int seen[1000];
//int parent[1000];
Item queue[1000];
Item *front;
Item *back;
//int front;
//int back;
int min(int a, int b)
{
return (a<b) ? a : b;
}
void push(Item val){
if (front == NULL)
{
front = new Item(val);
back = front;
}
else
{
back->next = new Item(val);
back = back->next;
}
}
Item pop(){
if (back != NULL)
{
Item ret(*front);
Item* temp = front;
front = front->next;
if (front == NULL)
back = NULL;
delete temp;
return ret;
}
}
bool queueEmpty()
{
return back == NULL;
}
void doFlow(int head, int flow)
{
for (Link* temp = graph[parent[head]]; temp != NULL; temp = temp->next)
{
if (temp->u == head)
{
temp->flow += flow;
temp->cosine->flow -= flow;
}
}
}
int run = 1;
void bfs(int n)
{
Item item;
item.u = n;
item.localResidue = 987654321;
item.next = NULL;
push(item);
Item nextItem;
nextItem.u = 0;
nextItem.localResidue = 987654321;
nextItem.next = NULL;
while (!queueEmpty())
{
Item i = pop();
seen[i.u] = 2;
//cout << i << endl;
for (Link *temp = graph[i.u]; temp != NULL; temp = temp->next)
{
if (seen[temp->u] == 0 && temp->capacity > temp->flow)
{
parent[temp->u] = i.u;
nextItem.u = temp->u;
nextItem.localResidue = min(i.localResidue, temp->capacity - temp->flow);
push(nextItem);
seen[temp->u] = 1;
if (nextItem.u == v + 1)
{
int head = v + 1;
while (head != 0)
{
doFlow(head, nextItem.localResidue);
head = parent[head];
}
run = 1;
return;
}
}
}
}
if (nextItem.u != v + 1)
{
run = 0;
}
}
void bfs_all()
{
for (int i = 0; i < v; i++)
if (seen[i] == 0)
bfs(i);
}
fstream fin;
int flow();
void flowInput(int a, int b, int c);
int main()
{
int n, flowAmount = 0;
char tmp;
fin.open("escape_input6.txt");
fin >> n;
v = n * n * 2;
graph = new Link*[v + 2];
seen = new int[v + 2];
parent = new int[v + 2];
memset(graph, 0, sizeof(Link*) * (v + 2));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
fin >> tmp;
if (tmp == '1') // 나오는곳인 경우
{
++flowAmount;
flowInput(0, ((i - 1) * n + j) * 2 - 1, 1); // 시작점과 연결
}
flowInput(((i - 1) * n + j) * 2 - 1, ((i - 1) * n + j) * 2, 1); // 자신의 기본 연결
if (i == 1 || i == n || j == 1 || j == n) // 끝나는 곳인 경우
{
flowInput(((i - 1) * n + j) * 2, n * n * 2 + 1, 1); // 끝점과 연결
}
if (i == 1) // 위 가장자리
{
DOWN(i, j)
if (j == 1) // 왼 가장 자리
{
RIGHT(i, j)
}
else if (j == n) // 오른 가장 자리
{
LEFT(i, j)
}
else
{
RIGHT(i, j)
LEFT(i, j)
}
}
else if (i == n) // 아래 가장 자리
{
UP(i, j)
if (j == 1) // 왼 가장 자리
{
RIGHT(i, j)
}
else if (j == n) // 오른 가장 자리
{
LEFT(i, j)
}
else
{
RIGHT(i, j)
LEFT(i, j)
}
}
else if (j == 1) // 왼 가장 자리
{
DOWN(i, j)
UP(i, j)
RIGHT(i, j)
}
else if (j == n) // 오른 가장 자리
{
DOWN(i, j)
UP(i, j)
LEFT(i, j)
}
else // 가장자리 아님
{
DOWN(i, j)
UP(i, j)
LEFT(i, j)
RIGHT(i, j)
}
}
int ret = flow();
std::cout << "start : " << flowAmount << ((ret == flowAmount) ? " = " : " != ") << "max : "<< ret << endl;
std::cout << ((ret == flowAmount) ? "escape success!!" : "escape fail!!") << endl;
}
void flowInput(int a, int b, int c)
{
//int a, b, c;
std::cout << a << " " << b << " " << c << endl;
Link *aLink = NULL;
Link *bLink = NULL;
bool isExist = false;
if (graph[a] == NULL)
{
graph[a] = new Link(b, c);
aLink = graph[a];
}
else
{
Link *temp = NULL;
for (temp = graph[a]; temp != NULL; temp = temp->next)
{
if (temp->u == b)
{
isExist = true;
temp->capacity = c;
}
}
if (!isExist)
{
for (temp = graph[a]; temp->next != NULL; temp = temp->next);
temp->next = new Link(b, c);
aLink = temp->next;
}
}
isExist = false;
if (graph[b] == NULL)
{
graph[b] = new Link(a, 0);
bLink = graph[b];
}
else
{
Link *temp = NULL;
for (temp = graph[b]; temp != NULL; temp = temp->next)
{
if (temp->u == a)
{
isExist = true;
break;
}
}
if (!isExist)
{
for (temp = graph[b]; temp->next != NULL; temp = temp->next);
temp->next = new Link(a, 0);
bLink = temp->next;
}
}
if (aLink && bLink)
{
aLink->cosine = bLink;
bLink->cosine = aLink;
}
}
int flow()
{
while (run)
{
front = NULL;
back = NULL;
/*
front = 0;
back = 0;*/
memset(seen, 0, sizeof(int) * (v + 3));
memset(parent, -1, sizeof(int) * (v + 3));
//memset(parent, -1, sizeof(parent));
//memset(seen, 0, sizeof(seen));
bfs(0);
while (!queueEmpty())
pop();
}
//for (int i = 1; i <= v; i++)
//{
// std::cout << parent[i] << endl;
//}
int result = 0;
for (Link *temp = graph[0]; temp != NULL; temp = temp->next)
{
result += temp->flow;
}
return result;
}
Longest Common Subsequence.cpp