Posted in ACM-ICPC, BFS, Kuangbin

POJ 3984/ kuangbin 1K/ maze problem

Problem: http://poj.org/problem?id=3984
Solution: BFS.

#include
#include
#include
#include
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 q;
stack 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 = 1 && m + dx[i] = 1 && n + dy[i] <= 5 && 
						a[m + dx[i]][n + dy[i]] == 0 && vis[m + dx[i]][n + dy[i]] == 0) {
				vis[m + dx[i]][n + dy[i]] = 1;
				T temp;
				temp.init(m + dx[i], n + dy[i]);
				prevx[m + dx[i]][n + dy[i]]	= m;
				prevy[m + dx[i]][n + dy[i]] = n;
				q.push(temp);
			}
		}
		bfs(q.front());
	}
}

int main () {
	for (int i = 1; i  a[i][j];
		}
	}
	T temp;
	temp.init(1, 1);
	prevx[temp.x][temp.y] = 0;
	prevy[temp.x][temp.y] = 0;
	vis[temp.x][temp.y] = 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;
}
Posted in BFS, Kuangbin

POJ 3126 Prime Path/ kuangbin 1F

12/23/2017
Problem: http://poj.org/problem?id=3126
Solution: BFS.

#include<iostream>
#include<queue>
#include<string.h> 
using namespace std;
int mp[10000];

struct node {
	int num, cnt;
	node(int numm, int cntt) {
		num = numm;
		cnt = cntt;
	}
};

queue<node> q;

bool prime(int n) {
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0) {
			return false;
		}
	}
	return true;
} 

void digit(node n) {
	int div = 0, rem = 0;
	int tmp = 1;	
	for (int i = 1; i <= 3; i++) {
		tmp *= 10;
		div = n.num / tmp;
		rem = n.num % (tmp / 10);
		for (int j = 0; j <= 9; j++) {
			int newNum = div * tmp + j * (tmp / 10) + rem;
			// cout << newNum << endl; 
			if (prime(newNum) && !mp[newNum]) {
				// cout << newNum << endl;
				q.push(node(newNum, n.cnt + 1)); 
				mp[newNum] = 1;
			} 
		}
	}
	rem = n.num % 1000;
	for (int j = 1; j <= 9; j++) {
		int newNum = j * 1000 + rem;
		if (prime(newNum) && !mp[newNum]) {
			// cout << newNum << endl; 
			q.push(node(newNum, n.cnt + 1));
			mp[newNum] = 1;
		}
	}
}

int main() {
	int n;
	cin >> n;
	while (n--) {
		int start = 0, end = 0;
		cin >> start >> end;
		memset(mp, 0, sizeof(mp));
		while (!q.empty()) {
			q.pop();
		}
		node head = node(start, 0);
		mp[start] = 1;
		q.push(head);
		while (!q.empty() && q.front().num != end) {
			digit(q.front());
			q.pop();
		}
		if (q.empty()) {
			cout << "Impossible" << endl; 
		} else {
			cout << q.front().cnt << endl;			
		}
	}
	return 0;
}
Posted in BFS, Kuangbin

POJ 1426/ kuangbin 1E

10/16/2017
Problem: http://poj.org/problem?id=1426
Solution: BFS. Manage a queue, and for each time push current number + 0 or 1 in
the end all the way untill curr is a multiple of given n. For some
mysterious reason limited to long long…


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

int main() {
	long long n;
	while (cin >> n) {
		if (n == 0) {
			break;
		}
		long long ans = 0;
		queue<long long> q;
		q.push(1);
		while (!q.empty()) {
			long long cur = q.front();
			q.pop();
			if (cur % n == 0) {
				cout << cur << endl;
				break;
			} else {
				q.push(cur * 10);
				q.push(cur * 10 + 1);
			}
		}
	}
	return 0;
} 

Posted in BFS, Kuangbin

POJ 3278/ kuangbin 1C

10/13/2017
Problem: http://poj.org/problem?id=3278
Solution: For every element x in the queue, add in x-1. x+1, x*2.


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

bool v[100005];

bool inrange(int x) {
	return (x >= 0) && (x <= 100000); 
}

struct node{
	int t;
	int x;
	node(int tt, int xx) {
		t = tt;
		x = xx;
	}
};

int main() {
	int n, k;
	cin >> n >> k;
	queue<node> q;
	q.push(node(0, n));
	v[n] = true;
	while(!q.empty()) {
		node curr = q.front();
		q.pop();
		if (curr.x == k) {
			cout << curr.t;
			return 0;
		}
		if (inrange(curr.x - 1) && !v[curr.x - 1]) {
			q.push(node(curr.t + 1, curr.x - 1));
			v[curr.x - 1] = true;
		} 
		if (inrange(curr.x + 1) && !v[curr.x + 1]) {
			q.push(node(curr.t + 1, curr.x + 1));
			v[curr.x + 1] = true;
		}
		if (inrange(curr.x * 2) && !v[curr.x * 2]) {
			q.push(node(curr.t + 1, curr.x * 2));
			v[curr.x * 2] = true;
		}
	}
	return 0;
} 

Posted in BFS, Kuangbin

POJ 2251 Dungeon Master/ kuangbin 1B

10/13/2017
Problem: http://poj.org/problem?id=2251
Solution: A plain bfs searching. Only changing 2D to 3D, but the usage is the strategy is the same.


#include<iostream>
#include<string.h>
#include<cstring>
#include<queue>
using namespace std;

int x, y, z;
int xs, ys, zs, xe, ye, ze;
int step = 0;
char map[35][35][35];
bool v[35][35][35];

int dx[10] = {1, 0, 0, -1, 0, 0}; 
int dy[10] = {0, 1, 0, 0, -1, 0}; 
int dz[10] = {0, 0, 1, 0, 0, -1}; 

struct node{
	int time;
	int x, y, z;
	node(int tt, int xx, int yy, int zz) {
		time = tt;
		x = xx;
		y = yy;
		z = zz;
	}
};

bool inrange(int xx, int yy, int zz) {
	return (xx >= 0 && yy >= 0 && zz >= 0 && xx < x && yy < y && zz < z);
}

bool bfs() {
	queue<node> q;
	q.push(node(0, xs, ys, zs));
	v[xs][ys][zs] = true;
	while (!q.empty()) {
		node curr = q.front();
		q.pop();
		if (curr.x == xe && curr.y == ye && curr.z == ze) {
			step = curr.time;
			return true;
		} else {
			for (int i = 0; i < 6; i++) {
				int xx = curr.x + dx[i];
				int yy = curr.y + dy[i];
				int zz = curr.z + dz[i];
				if (inrange(xx, yy, zz) && (map[xx][yy][zz] == '.' || map[xx][yy][zz] == 'E') && !v[xx][yy][zz]) {
					q.push(node(curr.time + 1, xx, yy, zz));
					v[xx][yy][zz] = true;
				}
			}
		}
	}
	return false;
}

int main() {
	while (cin >> x >> y >> z) {
		if (x == 0 && y == 0 && z == 0) {
			return 0;
		}
		memset(map, 0, sizeof(map));
		memset(v, 0, sizeof(v));
		for (int i = 0; i < x; i++) {
			for (int j = 0; j < y; j++) {
				cin >> map[i][j];
				for (int k = 0; k < z; k++) {
					if (map[i][j][k] == 'S') {
						xs = i;
						ys = j;
						zs = k;
					} else if (map[i][j][k] == 'E') {
						xe = i;
						ye = j;
						ze = k;
					}
				}
			}
		}
		if (bfs()) {
			cout << "Escaped in " << step << " minute(s).";
		} else {
			cout << "Trapped!";
		}
		cout << endl;
	}
	return 0;
}

Posted in DFS

PKU 24 Sticks

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


#include<iostream> 
#include<cstring>
#include<algorithm>
using namespace std;
int a[105] = {0};
bool v[105];
int sum = 0, m = 0, ans;
int len, num, n;

bool cmp(int x, int y) {
	return x > y; 
}

bool dfs(int stick, int l) {
	if (stick == num) {
		return true;
	}
	for (int i = 1; i <= n; i++) {
		if (!v[i]) {
			if (l + a[i] > len) {
				continue;
			} else if (l + a[i] == len) {
				v[i] = true;
				bool b = dfs(stick + 1, 0);
				v[i] = false;
				return b;
			} else {
				v[i] = true;
				bool b = dfs(stick, l + a[i]);
				v[i] = false;
				if (b) {
					return true;
				} else if (!b && l == 0) {
					return false;
				}
			}
		}
	}
	return false;
}

int main() {
	while (cin >> n) {
		memset(v, false, sizeof(v));
		memset(a, 0, sizeof(a));
		sum = 0;
		m = 0;
		if (n == 0) {
			return 0;
		}
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
			sum += a[i];
			if (a[i] > m) {
				m = a[i];
			}
		}
		sort(a + 1, a + n + 1, cmp);
		for (len = m; len <= sum; len++) {
			if (sum % len == 0) {
				num = sum / len;
				if (dfs(1, 0)) {
					cout << len << endl;
					break;
				}
			}
		}
	} 
}


Posted in DFS

PKU 23 Thailand Pagoda

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


#include<iostream>
#include<climits>
using namespace std;
int n, m;
int s;
int mins = INT_MAX;
int mv[21] = {0}; 

void dfs(int vol, int dep, int r, int h) {
	if (dep == 0) {
		if (vol == 0 && s < mins) {
			mins = s; 
		}
		return;
	}
	if (s >= mins || vol < mv[dep - 1] || s + 2 * vol / r >= mins) {
		return;
	} 
	for (int rr = r - 1; rr >= dep; rr--) {
		int hm = min(h - 1, (vol - mv[dep - 1]) / rr / rr);
		for (int hh = hm; hh >= dep; hh--) {
			if ((vol - rr * rr * hh) >= 0) {
				if (dep == m) {
					s = rr * rr;
				}
				s += 2 * rr * hh;
				dfs(vol - rr * rr * hh, dep - 1, rr, hh);
				s -= 2 * rr * hh;
				if (dep == m) {
					s = 0;
				}
			}
		}
	} 
}

int main() {
	for (int i = 1; i <= 20; i++) {
		mv[i] += mv[i - 1] + i * i * i; 
	} 
	while (cin >> n >> m) {
		mins = INT_MAX;
		dfs(n, m, n + 1, n + 1);
		if (mins == INT_MAX) {
			cout << 0 << endl;
		} else {
			cout << mins << endl;
		}
	}
	return 0;
}

Posted in BFS

PKU 21 MingRen and Zuozhu

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


#include<iostream>
#include<queue>
using namespace std;
string a[205];
bool v[205][205][15];
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[sx][sy][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][k.num - 1]) {
					if (k.num > 0) {
						q.push(node(x, y, k.num - 1, k.level + 1));
						v[x][y][k.num - 1] = true;
					} else {
						continue;
					}
				} else if (a[x][y] != '#' && !v[x][y][k.num]){
					q.push(node(x, y, k.num, k.level + 1));
					v[x][y][k.num] = true;
				}
			}
		}
	}
	cout << "-1";
	return 0;
} 

Posted in BFS

PKU 20 Rescue Operation

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


#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int v[205][205] = {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[205];
		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[nx][ny] != '#'	&& !v[nx][ny]) {
					if (a[nx][ny] == 'x') {
						v[nx][ny] = 1; 
						q.push(node(nx, ny, tmp.step + 2));
					} else {
						v[nx][ny] = 1; 
						q.push(node(nx, ny, tmp.step + 1));
					}
				}
			}
		}
		if (q.empty()) {
			cout << "Impossible" << endl;
		} else {
			cout << q.top().step << endl;
		}
	}
	return 0;	
}


Posted in 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; 
}