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

Posted in DFS

PKU 15 Red and Black

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


#include<iostream>
#include<cstring>
using namespace std;
string a[25];
bool visited[25][25];
int dx[5] = {-1, 0, 0, 1};
int dy[5] = {0, -1, 1, 0};
int w, h; 
int cnt = 0;

bool range(int x, int y) {
	// cout << x << ' ' << y << endl;
	if (x >= 0 && x < h && y >= 0 && y < w) {
		// cout << "true";
		return true;
	} 
	return false;
}

void dfs(int x, int y) {
	// cout << x << ' ' << y << ' ' << a[x][y] << ' ' << visited[x][y] << endl;
	if (range(x, y) && a[x][y] == '.' && !visited[x][y]) {
		// cout << x << ' ' << y << endl;
		cnt ++;
		visited[x][y] = true;	
		for (int i = 0; i < 4; i++) {
			int xx = x + dx[i];
			int yy = y + dy[i];
			dfs(xx, yy);
		} 			
	}
}

int main() {
	while (cin >> w >> h) {
		if (w == 0 && h == 0) {
			return 0;
		}
		cnt = 0;
		bool end = false;
		memset(visited, false, sizeof(visited));
		for (int i = 0; i < h; i++) {
			cin >> a[i];
		}
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (a[i][j] == '@') {
					// cout << i << ' ' << j << endl;
					a[i][j] = '.';
					dfs(i, j);
					cout << cnt << endl;
					end = true;
					break;
				}
			}
			if (end) {
				break;
			}
		}			
	}
	return 0;
}

Posted in DFS, Dynamic Programming

PKU 7 Skiing

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


#include<iostream>
#include<cstring>
using namespace std;
int a[105][105] = {0};
int dp[105][105] = {0};
int dx[5] = {-1, 0, 0, 1};
int dy[5] = {0, -1, 1, 0};
int r, c;

int dfs(int x, int y) {
	if (dp[x][y] > 0) {
		return dp[x][y];	
	}	
	int tmp = 0;
	for (int i = 0; i < 4; i++) {
		int xx = x + dx[i];
		int yy = y + dy[i];
		if (xx > 0 && xx <= r && yy > 0 && yy <= c && a[xx][yy] < a[x][y]) {
			tmp = max(tmp, dfs(xx, yy) + 1);
		}
	} 
	return tmp;
}

int main() {
	cin >> r >> c;
	for (int i = 1; i <= r; i++) {
		for (int j = 1; j <= c; j++) {
			cin >> a[i][j];
		}
	}
	int mx = 0;
	for (int i = 1; i <= r; i++) {
		for (int j = 1; j <= c; j++) {
			dp[i][j] = dfs(i, j);
			// cout << dp[i][j] << ' ';
			if (dp[i][j] > mx) {
				mx = dp[i][j];
			} 
		}
		// cout << endl;
	}
	cout << mx + 1;
	return 0;
}

Posted in DFS

POJ 2386 Lake Counting

2/16/2017
Problem: http://poj.org/problem?id=2386
Solution: Count the number of connected block


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

string a[105];
bool b[105][105];
int n, m;

void dfs(int x, int y) {
	for (int i = -1; i <= 1; i++) {
		for (int j = -1; j <= 1; j++) {
			if (x + i >= 0  && x + i < n && y + j >= 0 && y + j < m 
						&& a[x + i][y + j] == 'W' && !b[x + i][y + j]) {
				b[x + i][y + j] = true;
				dfs(x + i, y + j);
			}
		}
	}
}

int main() {
	memset(b, false, sizeof(b));
	int count = 0;
	cin >> n >> m;
	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] == 'W' && !b[i][j]) {
				dfs(i, j);
				count ++;
			}
		}
	}
	cout << count;
	return 0;
}

Posted in DFS

CF 793B Igor and his way to work

4/23/2017
Problem: http://codeforces.com/problemset/problem/793/B
Solution: 3-D DFS. Need an extra dimension to represent if it has been to the
point with one turn or two.


#include<iostream>
using namespace std;

string s[1005];
int m, n;
int sx, sy;
int dx[4] = {-1, 0, 0, 1};
int dy[4] = {0, -1, 1, 0};
bool visited[1005][1005][3];

int getDirection(int dx, int dy) {
	if (dx == -1 && dy == 0) {
		return 1;
	} else if (dx == 0 && dy == -1) {
		return 2;
	} else if (dx == 0 && dy == 1) {
		return 3;
	} else {
		return 4;
	}	
}

bool dfs(int x, int y, int turn, int dir) {
	// cout << x << ' ' << y << ' ' << turn << endl;
	if (turn <= 2 && x >= 0 && x < m && y >= 0 && y < n && s[x][y] != '*' && !visited[x][y][turn]) {
		visited[x][y][turn] = true;
		if (s[x][y] == 'T') {
			return true;
		}
		for (int i = 0; i < 4; i++) {
			if (dir != getDirection(dx[i], dy[i])) {
				if (dfs(x + dx[i], y + dy[i], turn + 1, getDirection(dx[i], 
											dy[i]))) {
					return true;
				}
			}else {
				if (dfs(x + dx[i], y + dy[i], turn, getDirection(dx[i], 
											dy[i]))) {
					return true;
				}				
			}

		}		
	}
	return false;
}

int main () {
	cin >> m >> n;
	for (int i = 0; i < m; i++) {
		cin >> s[i];
	}
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (s[i][j] == 'S') {
				sx = i; 
				sy = j;
			}
		}
	}
	// cout << sx << ' ' << sy << endl;
	if (dfs(sx, sy, -1, 0)) {
		cout << "YES" << endl;
		return 0;
	}
	cout << "NO" << endl;
	return 0;
}

Posted in DFS

CF 771A Bear and Friendship Condition

7/5/2017
Problem: http://codeforces.com/problemset/problem/771/A


#include<iostream>
#include<vector>
#define ll long long
using namespace std;
int n, m;
vector<int> mp[150005];
bool v[150005];

void dfs(int i, int & p, int & e) {
	v[i] = true;
	p ++;
	e += mp[i].size();
	vector<int>::iterator it;
	for (it = mp[i].begin(); it != mp[i].end(); ++it) {
		if (!v[*it]) {
			dfs(*it, p, e);
		}
	}
}

int main () {
	cin >> n >> m;
	while (m--) {
		int x, y;
		cin >> x >> y;
		mp[x].push_back(y);
		mp[y].push_back(x);
	}
	for (int i = 1; i <= n; i++) {
		if (!v[i]) {
			int p = 0, e = 0;
			dfs(i, p, e);
			if ((ll)p * (ll)(p - 1) != (ll)e) {
				cout << "NO";
				return 0;
			}
		}	
	}
	cout << "YES";
	return 0;
}

Posted in DFS

CF 580C Kefa and Park

2017/1/6
Problem: http://codeforces.com/problemset/problem/580/C
Solution: Use adjacency list to record all paths, then dfs to count cats along
the way.
Note:
1. mix up arrays starting from 0 and 1
2. get confused on the logic: it should be “Nodes that all related paths
are parent is a root node.”


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

int n,m;
int c[100005] = {0};
int ans = 0;
vector<int> a[100005];

void dfs(int p, int father, int cat) {
	if (cat > m) {
		return;
	} else {
		int b = 0;
		for (int i = 0; i <= a[p].size()-1; i++) {
			if (a[p][i] != father) {
				b = 1;
				if (c[a[p][i]] == 1) {
					dfs(a[p][i], p, cat + 1);
				} else {
					dfs(a[p][i], p, 0);
				}
			}
		}
		if (b == 0) {
			ans ++;
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> c[i];
	} 
	for (int i = 1; i <= n-1; i++) {
		int l, r;
		cin >> l >> r;
		a[l].push_back(r);
		a[r].push_back(l);
	}
	dfs(1, 0, c[1]);
	cout << ans;
	return 0;
} 

Posted in DFS

CF 522A Reposts

7/5/2017
Problem: http://codeforces.com/problemset/problem/522/A
Others: Suddenly want to try JAVA – -AC on first attempt.. wow


import java.io.*;
import java.util.*;

public class test {

    public static Map<String, Set<String>> mp = new HashMap();
    public static int max = 0;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        for (int i = 1; i <= n; i++) {
            String s1, s2, s3;
            s1 = in.next();
            s2 = in.next();
            s3 = in.next();
            // System.out.println(s1);
            if (!mp.containsKey(s3.toLowerCase())) {
                Set<String> tmp = new HashSet();
                mp.put(s3.toLowerCase(), tmp);
            }
            mp.get(s3.toLowerCase()).add(s1.toLowerCase());
            //System.out.println(mp.get(s3));
        }
        // System.out.println(mp.get("tourist"));
        dfs("polycarp", 2);
        System.out.println(max);
    }

    public static void dfs(String s, int depth) {
        if (mp.get(s) != null) {
            // System.out.println(mp.get(s));
            for (String r: mp.get(s)) {
                // System.out.println(r);
                if (depth > max) {
                    max = depth;
                }
                dfs(r, depth + 1);
            }
        }
    }

}