Tags » BF's

Niepokój

23:02, wtorek, 15 sie 2017. Miejsce: Hotel Mainport Rotterdam.

Pisanie daje mi iluzoryczne poczucie kontroli nad chaosem. Czarna dziura którą próbuję ujeżdżać jak byka. Spadam z tego byka za każdym razem i rozbijam łeb. 462 more words

LeetCode Topological Sorting 系列

Topological sorting 是有向圖的應用,以下為拓樸排序的例子

Given an directed graph, a topological order of the graph nodes is defined as follow:

  • For each directed edge A -> B in graph, A must before B in the order list.
434 more words

The Summer Goddess - BFS Nomination Goodreads Giveaway!

To celebrate the fact that The Summer Goddess has been shortlisted for Best Novel at this years British Fantasy Society Awards (alongside Adrian Tchaikovsky, Jen Williams and Steven Poore), I’ve decided to run a Goodreads giveaway where you can win a FREE copy! 49 more words

Books

PKU 21 MingRen and Zuozhu

Problem: http://acmicpc.openjudge.cn/practice/021/


#include<iostream>
#include<queue>
using namespace std;
string a;
bool v;
int dx[5] = {-1, 0, 0, 1};
int dy[5] = {0, -1, 1, 0};
int n, m, t;

struct node {
	int x;
	int y;
	int num;
	int level;
	node(int xx, int yy, int numm, int levell) {
		x = xx;
		y = yy;
		num = numm;
		level = levell;
	}
};

bool inrange(int x, int y) {
	if (x >= 0 && x < m && y >= 0 && y < n) {
		return true;
	} 
	return false;
}

int main() {
	cin >> m >> n >> t;
	for (int i = 0; i < m; i++) {
		cin >> a[i];
	}
	int sx, sy;
	int ex, ey;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (a[i][j] == '@')	{
				sx = i;
				sy = j;
			} else if (a[i][j] == '+') {
				ex = i;
				ey = j;
			}
		}
	}
	queue<node> q;
	q.push(node(sx, sy, t, 0));
	v[t] = true;
	while(!q.empty()) {
		node k = q.front();
		q.pop();
		if (k.x == ex && k.y == ey) {
			cout << k.level;
			return 0;
		}
		for (int i = 0; i < 4; i++) {
			int x = k.x + dx[i];
			int y = k.y + dy[i];
			if (inrange(x, y)) {
				if (a[x][y] == '#' && !v[x][y]) {
					if (k.num > 0) {
						q.push(node(x, y, k.num - 1, k.level + 1));
						v[x][y] = true;
					} else {
						continue;
					}
				} else if (a[x][y] != '#' && !v[x][y]){
					q.push(node(x, y, k.num, k.level + 1));
					v[x][y] = true;
				}
			}
		}
	}
	cout << "-1";
	return 0;
} 12 more words
BFS

PKU 20 Rescue Operation

Problem: http://acmicpc.openjudge.cn/practice/020/


#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int v = {0};
int dx[4] = {-1, 0, 0, 1};
int dy[4] = {0, -1, 1, 0};
int n, m;

struct node {
	int x;
	int y;
	int step;
	node(int tmpx, int tmpy, int tmpstep) {
		x = tmpx;
		y = tmpy;
		step = tmpstep;
	}
};

bool inrange(int x, int y) {
	if (x >= 0 && x < n && y >= 0 && y < m) {
		return true;
	}
	return false;
}

bool operator<(node a, node b) {
	return a.step > b.step;
}

int main() {
	int s;
	cin >> s;
	while (s--) {
		memset(v, 0, sizeof(v));
		priority_queue<node> q;
		int x, y, xx, yy;
		cin >> n >> m;	
		string a;
		for (int i = 0; i < n; i++) {
			cin >> a[i];
		}	
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (a[i][j] == 'r') {
					x = i;
					y = j;
				}
				if (a[i][j] == 'a') {
					xx = i;
					yy = j;
				}
			}
		}
		q.push(node(x, y, 0));
		v[x][y] = 1;
		while (!q.empty() && !(q.top().x == xx && q.top().y == yy)) {
			node tmp = q.top();
			// cout << tmp.x << ' ' << tmp.y << endl;
			q.pop();
			for (int i = 0; i < 4; i++) {
				int nx = tmp.x + dx[i];
				int ny = tmp.y + dy[i];
				if (inrange(nx, ny) && a != '#'	&& !v) {
					if (a == 'x') {
						v = 1; 
						q.push(node(nx, ny, tmp.step + 2));
					} else {
						v = 1; 
						q.push(node(nx, ny, tmp.step + 1));
					}
				}
			}
		}
		if (q.empty()) {
			cout << "Impossible" << endl;
		} else {
			cout << q.top().step << endl;
		}
	}
	return 0;	
} 10 more words
BFS

PKU 19 Word Ladders

Problem: http://acmicpc.openjudge.cn/practice/019/


#include<iostream>
#include<queue>
#include<set>
using namespace std;
set<string> visit;

struct node{
	int step;
	string s;
	node(string ss, int num) {
		step = num;
		s = ss;
	}
};

bool compare(string s1, string s2) {
	int len = s1.length();
	int cnt = 0;
	for (int i = 0; i < len; i++) {
		if (s1[i] != s2[i]) {
			cnt ++;
		}
	}
	return cnt == 1;
}

int main() {
	string s1, s2;
	set<string> st;
	cin >> s1 >> s2;
	st.insert(s1);
	st.insert(s2);
	string s;
//	for (int i = 1; i <= 5; i++) {
//		cin >> s;
//		st.insert(s); 
//	}
	while (cin >> s) {
		st.insert(s);
	}
	queue<node> q;
	q.push(node(s1, 1));
	while (!q.empty() && q.front().s != s2) {
		node tmp = q.front();
		q.pop(); 
		visit.insert(tmp.s); 
		set<string>::iterator it;
		for (it = st.begin(); it != st.end(); ++it) {
			if (visit.find(*it) == visit.end() && compare(tmp.s, *it)) {
				// cout << *it << ' ' << tmp.step + 1 << endl;
				q.push(node(*it, tmp.step + 1));
			}
		} 
	}
	if (q.empty()) {
		cout << 0;
		return 0;
	}
	cout << q.front().step;
	return 0; 
} 

BFS

POJ 3984 Maze

2/17/2017
Problem: http://poj.org/problem?id=3984
Solution: Maze problem. To find the shortest way, use BFS.


#include<iostream>
#include<queue>
#include<stack>
#include<cstring>
using namespace std;

int a[6][6] = {0};
int vis[6][6] = {0};
int dx[5] = {0, -1, 0, 1, 0};
int dy[5] = {0, 0, -1, 0, 1};
int prevx[6][6] = {0};
int prevy[6][6] = {0};

struct T {
	int x;
	int y;
	void init(int a, int b) {
		x = a;
		y = b;
	}
};

queue<T> q;
stack<T> ans;

void print(int x, int y) {
	if (x != 0 || y != 0) {
		T temp;
		temp.init(x, y);
		ans.push(temp);
		print(prevx[x][y], prevy[x][y]);
	}
}

void bfs(T temp) {
	int m = temp.x;
	int n = temp.y;
	if (m == 5 && n == 5) {
		print(m, n);
	} else {
		q.pop();
		for (int i = 1; i <= 4; i++) {
			if (m + dx[i] >= 1 && m + dx[i] <= 5 && n + dy[i] >= 1 && n + dy[i] <= 5 && 
						a]] == 0 && vis]] == 0) {
				vis]] = 1;
				T temp;
				temp.init(m + dx[i], n + dy[i]);
				prevx]]	= m;
				prevy]] = n;
				q.push(temp);
			}
		}
		bfs(q.front());
	}
}

int main () {
	for (int i = 1; i <= 5; i ++) {
		for (int j = 1; j <= 5; j ++) {
			cin >> a[i][j];
		}
	}
	T temp;
	temp.init(1, 1);
	prevx = 0;
	prevy = 0;
	vis = 1;
	q.push(temp);
	bfs(temp);
	while(!ans.empty()) {
		cout << '(' << ans.top().x - 1 << ", " << ans.top().y - 1 << ')';
		ans.pop();
		if (!ans.empty()) {
			cout << endl;
		}
	}
	return 0;
} 42 more words
BFS