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, Kuangbin

PKU 17/ POJ 1321/ kuangbin 1A/ Chessboard

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


#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
bool col[10];
string a[10];
long long ans = 0;
int n, k;

void dfs(int level, int cnt) {
	if (cnt >= k) {
		ans++;
		return;
	}
	if (level == n) {
		return;
	}
	for (int i = level ; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (!col[j] && a[i][j] == '#') {
				col[j] = true;
				dfs(i + 1, cnt + 1);
				col[j] = false; 
			}
		}
	}
	return;
}

int main() {
	ios::sync_with_stdio(false);
	while (cin >> n >> k) {
		if (n == -1 && k == -1) {
			return 0;
		} 
		memset(col, false, sizeof(col));
		ans = 0;
		for (int i = 0; i < n; i++) {
			cin >> a[i];
		}
		dfs(0, 0);
		cout << ans << endl;
	} 
	return 0;
}