f677: FJCU_109_Winter_Day3_Lab1 並查集練習

解題心得

為了方便直接看 num[0] 就知道是答案， union 的時候要讓 index 大的指到小的。

程式碼

#include <iostream>
using namespace std;

int p[1000] = { 0 }, num[1000] = { 0 };
int find_set(int u)
{
	if (p[u] == u) return u;
	return p[u] = find_set(p[u]);
}
int main()
{
	int n, m, a, b;
	cin >> n >> m;

	for (int i = 0; i < n; i++)
		p[i] = i, num[i] = 1;
	while (m--)
	{
		cin >> a >> b;
		a = find_set(a), b = find_set(b);
		if (a != b)
		{
			if (b > a)
				swap(a, b);
			p[a] = b; // a 指到 b
			num[b] += num[a];
		}
	}
	cout << num[0] << endl;
	return 0;
}

f260: 愛八卦的同學

解題心得

這題沒給 n 的大小，好像不合理.....

而且最後用黑魔法才過的。

程式碼

#include <iostream>
using namespace std;

int f[10000] = { 0 }, Size[10000] = { 0 };

int find_set(int v)
{
	if (f[v] == v) return v;
	return f[v] = find_set(f[v]);
}
void union_by_size(int u, int v)
{
	/*if (Size[u] > Size[v])
		swap(u, v);
	Size[v] += Size[u];*/
	f[u] = v;
}
int main()
{
	cin.sync_with_stdio(false);
	cin.tie(NULL);
	int n, k, a, b;
	while (cin >> n >> k)
	{
		int group = n; // 幾個小圈圈
		for (int i = 0; i < n; i++)
			f[i] = i, Size[i] = 1;
		while (k--)
		{
			cin >> a >> b;
			a = find_set(a), b = find_set(b);
			if (a != b)
			{
				group--;
				union_by_size(a, b);
			}
		}
		cout << group << endl;
	}
	return 0;
}

d831: 畢業旅行

解題心得

額外開一個陣列來記錄該 set 的數量，要找 root(老大) 才是最新的數量。

程式碼

#include <iostream>
using namespace std;

int n, p[1000000] = { 0 }, num[1000000] = { 0 };

int find_set(int v)
{
	if (p[v] == v) return v;
	return p[v] = find_set(p[v]);
}
void init()
{
	for (int i = 0; i < 1000000; i++)
		p[i] = i, num[i] = 1;
}

int main()
{
	int m, a, b;
	while (cin >> n >> m)
	{
		int ans = 1;
		init();
		while (m--)
		{
			cin >> a >> b;
			a = find_set(a), b = find_set(b);
			if (a != b)
			{
				num[b] += num[a];
				p[a] = b; // a 指向 b
				ans = max(ans, num[b]);
			}
		}
		cout << ans << endl;
	}

	return 0;
}

a445: 新手訓練系列- 我的朋友很少

解題心得

disjoint set 練習。

完成 union(a,b), find_set(v), same_set(u, v) 就差不多能過了，只是 find_set 可以再進一步優化。

程式碼

#include <iostream>
using namespace std;

int n, m, q, f[10001] = { 0 };

void Union(int a, int b)
{
	f[a] = b;
}
int find_set(int v)
{
	while (f[v] != v)
		v = f[v];
	return f[v];
}
bool same_set(int a, int b)
{
	return find_set(a) == find_set(b);
}
int main()
{
	int a, b;
	cin >> n >> m >> q;

	for (int i = 1; i <= n; i++)
		f[i] = i;
	while (m--)
	{
		cin >> a >> b;
		Union(find_set(a), find_set(b));
	}
	while (q--)
	{
		cin >> a >> b;
		if (same_set(a, b))
			cout << ":)" << endl;
		else
			cout << ":(" << endl;
	}
	return 0;
}

d432: 第四題：通關密語 (pwd)

解題心得

跟上一題差不多。

程式碼

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

map<char, int> m;
string inOrder, postOrder;

void printPreorder(int start, int end)
{
	if (start > end) return;

	int val = -1, flag = -1;
	for (int i = start; i <= end; i++)
	{
		if (m[inOrder[i]] > val)
		{
			val = m[inOrder[i]];
			flag = i;
		}
	}
	cout << inOrder[flag];

	printPreorder(start, flag - 1);
	printPreorder(flag + 1, end);
}

int main()
{
	cin >> inOrder >> postOrder;
	for (int i = 0; i < postOrder.length(); i++)
		m[postOrder[i]] = i;
	printPreorder(0, postOrder.length() - 1);
	return 0;
}

d861: NOIP2001 3.求先序排列

解題心得

首先，先搞清楚中序跟後序等表示法。

中序: 左子樹、自己、右子樹；後序: 左子樹、右子樹、自己；前序: 自己、左子樹、右子樹。

因此要找「自己」，也就是前序表示法，要參考中序與後序提供的資訊。

要找到當前字串的「自己」，很明顯就是最右邊的字母。接下來要分別往左右子樹搜尋，則要利用中序字串來切割，遞迴下去。

所以每次都要找當前中序字串位於後序表達式中最右邊的字母，找到以後以它為基準，在中序字串中往左跟往右遞迴搜尋。為了方便計算，提前記錄好字母的位置，用一個大小為26的陣列紀錄所有大寫字母。

因為不存在於輸入的字母不會被存取到，直接擺零即可。

我都是看別人教學才會。

程式碼

#include <iostream>
using namespace std;

string inOrder, postOrder;
int order[26] = { 0 };
void printPreorder(int start, int end)
{
	if (start <= end)
	{
		int flag = -1, val = -1;
		for (int i = start; i <= end; i++)
		{
			if (order[inOrder[i] - 'A'] > val)
			{
				val = order[inOrder[i] - 'A'];
				flag = i;
			}
		}
		cout << inOrder[flag];//<< start << " " << flag << " " << flag + 1 << " " << end << endl;
		printPreorder(start, flag - 1);
		printPreorder(flag + 1, end);
	}
}
int main()
{
	
	cin >> inOrder >> postOrder;
	int start = 0, end = postOrder.length() - 1;
	for (int i = 0; i < postOrder.length(); i++)
		order[postOrder[i] - 'A'] = i;
	printPreorder(start, end);
	return 0;
}

f673: FJCU_109_Winter_Day2_Lab1 樹高

解題心得

用 array 存 node，找高度從 root 往下走直到 leaf node，leaf node 要回傳 0 給 parent，parent 選最大的加一後再往上丟。

程式碼

#include <iostream>
using namespace std;

struct Node
{
	int left, right;
};
Node tree[31];

int height(int index)
{
	if (index == -1)
		return 0;
	else
	{
		int leftHeight = height(tree[index].left);
		int rightHeight = height(tree[index].right);
		if (leftHeight > rightHeight) return leftHeight + 1;
		else return rightHeight + 1;
	}
}

int main()
{
	int n, u, a, b, root = -1;
	cin >> n;
	while (n--)
	{
		cin >> u >> a >> b;
		tree[u].left = a; tree[u].right = b;

		if (root == -1) root = u;
	}
	cout << height(root) - 1 << endl;
	return 0;
}

f675: FJCU_109_Winter_Day2_Lab3 二元搜尋樹

解題心得

二元搜尋樹的練習，中規中矩。

程式碼

#include <iostream>
using namespace std;

struct Node
{
	int data;
	Node* left; Node* right;
};
Node* insert(Node* tree, int n)
{
	if (tree == NULL)
	{
		tree = new Node;
		tree->data = n;
		tree->left = tree->right = NULL;
	}
	else
	{
		if (n < tree->data)
			tree->left = insert(tree->left, n);
		else
			tree->right = insert(tree->right, n);
	}
	return tree;
}

void printInorder(Node* tree)
{
	if (tree == NULL) return;

	printInorder(tree->left);
	cout << tree->data << endl;
	printInorder(tree->right);
}
bool search(Node* tree, int val)
{
	if (tree == NULL) return false;

	if (tree->data == val) return true;
	if (val < tree->data) search(tree->left, val);
	else search(tree->right, val);
}

int main()
{
	Node* root = NULL;
	int n, val, m;
	while (cin >> n)
	{
		while (n--)
		{
			cin >> val;
			root = insert(root, val);
		}
		printInorder(root);
		cin >> m;
		if (search(root, m))
			cout << "Yes" << endl;
		else cout << "No" << endl;
	}
	return 0;
}

d526: Binary Search Tree (BST)

解題心得

在 insert function 要回傳 tree node 這邊卡超久，一開始沒加，還想說為什麼都沒被更新到。

後來才搞清楚丟到function裡的是a copy of pointer，兩個指標指到同樣的位置(此處為null)，如果要有預期的行為，就需要把function裡的pointer更新回去。 同理，動到left node跟right node也要接收遞迴函式的回傳值。

比對以前寫的類似的程式，才恍然大悟為什麼以前會用class寫──因為就不是copy一份過去了。

程式碼

#include <iostream>
using namespace std;
struct Node
{
	int data;
	Node* left; Node* right;
};

Node* insert(Node* tree, int val)
{
	
	if (tree == NULL)
	{
		tree = new Node;
		tree->data = val;
		tree->left = tree->right = NULL;
	}
	else
	{
		if (val < tree->data)
			tree->left = insert(tree->left, val);
		else
			tree->right = insert(tree->right, val);
	}
	return tree;
}

void printPreorder(Node* tree)
{
	if (tree == NULL) return;

	cout << tree->data << " ";
	printPreorder(tree->left);
	printPreorder(tree->right);
}

int main()
{
	int n, temp;
	while (cin >> n)
	{
		Node* root = NULL;
		while (n--)
		{
			cin >> temp;
			root = insert(root, temp);
		}
		printPreorder(root);
		cout << endl;
	}
	return 0;
}

d119: 有獎徵答：換零錢

解題心得

題目寫得很亂，就沒有仔細看了。

基本上就是零錢問題，記得字串切割跟最後答案要-1就好。

程式碼

#include <iostream>
#include <string>
#include <sstream>
using namespace std;

int prices[10] = { 1,5,10,20,50,100,200,500,1000,2000 };
long long int ans[50001] = { 1 };

int main()
{
	for (int i = 0; i < 10; i++)
	{
		for (int j = prices[i]; j < 50001; j++)
			ans[j] += ans[j - prices[i]];
	}
	string s;
	while (getline(cin, s))
	{
		int n = 0, temp;
		stringstream ss(s);
		while (ss >> temp)
			n += temp;
		if (n == 0) break;
		cout << ans[n] - 1 << endl;
	}
	return 0;
}

b232: TOI2009 第四題：分房子

解題心得

這題也是硬幣問題(或者說解不等式問題?)，硬幣數是奇數。

記得開long long。

程式碼

#include <iostream>
using namespace std;

int prices[376];
long long int ans[751] = { 1,0 };

int main()
{
	for (int i = 0; i < 376; i++)
		prices[i] = i * 2 - 1;
	for (int i = 1; i <= 375; i++)
	{
		for (int j = prices[i]; j < 751; j++)
			ans[j] += ans[j - prices[i]];
	}
	int m, n;
	while (cin >> m)
	{
		while (m--)
		{
			cin >> n;
			cout << ans[n] << endl;
		}
		cout << endl;
	}
	return 0;
}

d289: 多元一次方程式

解題心得

這題就是零錢問題，或者說零錢問題的本質就是解不等式(?

程式碼

#include <iostream>
using namespace std;

int prices[8] = { 1,13,33,43,139,169,1309,2597 };
int ans[8001] = { 1,0 };

int main()
{
	for (int i = 0; i < 8; i++)
	{
		for (int j = prices[i]; j < 8001; j++)
			ans[j] += ans[j - prices[i]];
	}

	int l;
	while (cin >> l)
		cout << ans[l] << endl;
	return 0;
}

d253: 00674 - Coin Change

解題心得

想法類似於：前一種金額的方法數加一(?)

參考這裡

程式碼

#include <iostream>
using namespace std;

int prices[5] = { 1,5,10,25,50 };
int c[7490] = { 1,0 };


int main()
{
	for (int i = 0; i < 5; i++)
	{
		for (int j = prices[i]; j <= 7489; j++)
			c[j] += c[j - prices[i]];
	}
	int n;
	while (cin >> n)
		cout << c[n] << endl;
	return 0;
}

d904: 換零錢

解題心得

price放幣值種類，大小順序不重要。

每次單看一種種類的幣值，把1~c的目標金額都算過一次，如果新的(也就是扣掉自己的那個金額再加一)比現在需要的硬幣少，就更新。

參考這個跟這個網站。

程式碼

#include <iostream>
using namespace std;

int price[11] = { 0 }, money[1001] = { 0 };

int main()
{
	int c, n;
	while (cin >> c >> n)
	{
		for (int i = 0; i < n; i++)
			cin >> price[i];
		for (int i = 1; i < 1001; i++)
			money[i] = 1000000;
		for (int i = 0; i < n; i++)
		{
			for (int j = price[i]; j <= c; j++)
			{
				money[j] = min(money[j], money[j - price[i]] + 1);
			}
		}
		if (money[c] != 1000000) cout << money[c] << endl;
	}
	return 0;
}

d887: 1.山脈種類(chain)

解題心得

連續寫了幾題，對怎麼分析好像稍微有點感覺了。雖然還是不會寫。

DP的精神就是切割成小問題，這題的切法是想：曲線第一次的落地點在哪？

山的總長度為2n，因此落地可在2n, 2n-2, 2n-4, ......, 0。

程式碼

#include <iostream>
using namespace std;

int main()
{
	long long int memo[26] = { 1,0 }, n;
	for (int i = 1; i < 26; i++)
	{
		for (int j = 0; j < i; j++)
			memo[i] += memo[j] * memo[i - 1 - j];
	}
	while (cin >> n)
	{
		cout << memo[n] << endl;
	}
	return 0;
}

a111: 12149 - Feynman

解題心得

總是沒辦法自己想出來......紀錄一下推導。

以 4*4 的方形為例，會有：

1*1 的方形，共 16 個

2*2 的方形，共 9 個

3*3 的方形，共 4 個

4*4 的方形，共 1 個

基本邏輯就是把1~n邊長都找過一遍，看這樣的情況下能有幾種可能。又長度為i的情況下，會有(n-i)*(n-i)的可能，也就剛好是1^2+2^2+3^3+.....+n^2了。

用dp的話，就把每次結果存起來，算當下的就是把前一個加上自己的n^2就好。

程式碼 

#include <iostream>
using namespace std;

int main()
{
	int memo[101] = { 0,1 }, n;
	for (int i = 2; i < 101; i++)
		memo[i] = memo[i - 1] + i * i;
	while (cin >> n && n != 0)
		cout << memo[n] << endl;
	return 0;
}

d054: 11310 - DELIVERY DEBACLE

解題心得

參考了這個網站

程式碼

#include <iostream>
using namespace std;

int main()
{
	long long int memo[41] = { 1,1,5 };
	for (int i = 3; i <= 40; i++)
		memo[i] = memo[i - 1] + 4 * memo[i - 2] + 2 * memo[i - 3];
	int t, n;
	cin >> t;
	while (t--)
	{
		cin >> n;
		cout << memo[n] << endl;
	}
	return 0;
}

d038: 00900 - Brick Wall Patterns

解題心得

這題的本質就是 fib ，原因是要找 n 能有幾種拼法，就是把 n-1 的所有方法再加上直立的一個磚塊，以及 n-2 的所有方法再加上兩個平躺磚塊。

網路上的解法比較多是事先建表。我的寫法是每次都會查表，而若以前做過就不會重做。

程式碼

#include <iostream>
using namespace std;

long long int memo[51] = { 0 };
long long int f(int n)
{
	if (memo[n] != 0) return memo[n];
	if (n <= 2) return n;
	memo[n] = f(n - 1) + f(n - 2);
	return memo[n];
}
int main()
{
	int n;
	while (cin >> n)
	{
		if (n == 0) break;
		cout << f(n) << endl;
	}
	return 0;
}

e550: 00722 - Lakes

解題心得

輸入很麻煩的題目。

程式碼

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

struct Point
{
	int x, y;
};

char map[100][100];
int main()
{
	int T, dx[4] = { -1,1,0,0 }, dy[4] = { 0,0,-1,1 };
	cin >> T;
	while (T--)
	{
		int i, j, n = 0, m = 0, area = 0;
		string s;
		cin >> i >> j;
		i -= 1, j -= 1;
		getline(cin, s);

		while (getline(cin,s) && s.size())
		{
			for (int i = 0; i < s.size(); i++)
				map[m][i] = s[i];
			n = s.size();
			m++;
		}
		Point start, now;
		queue<Point> q;
		start.x = i, start.y = j;
		map[start.x][start.y] = '@';
		q.push(start);
		while(!q.empty())
		{
			now = q.front(); q.pop();
			//cout << now.x << " " << now.y << endl;
			area++;
			for (int i = 0; i < 4; i++)
			{
				Point p;
				p.x = now.x + dx[i], p.y = now.y + dy[i];
				//cout << "--" << p.x << " " << p.y << endl;
				if (p.x >= 0 && p.x < m && p.y >= 0 && p.y < n && map[p.x][p.y] == '0')
				{
					map[p.x][p.y] = '@';
					q.push(p);
				}
			}
		}
		cout << area << endl;
	}
	return 0;
}

c129: 00572 – Oil Deposits

解題心得

因為沒有固定的起始點，所以這樣寫(?

程式碼

#include <iostream>
using namespace std;

char map[101][101];
bool isVisited[101][101] = { false };
int m, n;

void bfs(int x, int y, char c)
{
	map[x][y] = 'x';
	isVisited[x][y] = true;
	int dx[8] = { -1,-1,-1,0,0,1,1,1 } , dy[8] = { -1,0,1,-1,1,-1,0,1 };
	for (int i = 0; i < 8; i++)
	{
		int nextX = x + dx[i], nextY = y + dy[i];
		if (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n && map[nextX][nextY] == c && !isVisited[nextX][nextY])
			bfs(nextX, nextY, c);
	}
}
int main()
{
	int counter = 1;
	

	while (cin >> m >> n)
	{
		if (m == 0 && n == 0) break;
		for (int i = 0; i < 101; i++)
			for (int j = 0; j < 101; j++)
				isVisited[i][j] = false;
		for (int i = 0; i < m; i++)
			for (int j = 0; j < n; j++)
				cin >> map[i][j];

		int ans = 0;
		for (int i = 0; i < m; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (map[i][j] == '@' && !isVisited[i][j])
					bfs(i, j, '@'), ans++;
			}
		}
		cout << ans << endl;
	}

	return 0;
}

d406: 倒水時間

解題心得

在dfs的「探索相鄰節點」步驟除了一一列舉外，還有更簡潔的寫法，就是將座標所需的位移裂成矩陣，迴圈檢查合法與否即可。

程式碼

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

int map[101][101] = { 0 };
struct Point
{
	int x, y, step = -1;
};

int main()
{
	int s, n, m, counter = 1;
	while (cin >> s)
	{
		cin >> n >> m;
		bool isVisited[101][101] = { false };
		Point start, now;
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				cin >> map[i][j];
				if (i == 0 && map[i][j] == 1)
					start.x = i, start.y = j;
			}
		}
		queue<Point> q;
		isVisited[start.x][start.y] = true;
		start.step = 1;
		q.push(start);
		int dx[4] = { 1,0,0,-1 }, dy[4] = { 0,1,-1,0 }; // 最後一個是往上
		while (!q.empty())
		{
			now = q.front(); q.pop();
			for (int i = 0; i < 4; i++)
			{
				if (i == 3 && s == 2) break;
				Point p;
				p.x = now.x + dx[i]; p.y = now.y + dy[i];
				if (p.x >= 0 && p.x < n && p.y >= 0 && p.y < m && map[p.x][p.y] != 0 && !isVisited[p.x][p.y])
				{
					isVisited[p.x][p.y] = true;
					p.step = now.step + 1;
					map[p.x][p.y] = p.step;
					q.push(p);
				}
				
			}
			isVisited[now.x][now.y] = true;
		}
		cout << "Case " << counter++ << ":" << endl;
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (map[i][j] != 0 && !isVisited[i][j]) cout << 0;
				else cout << map[i][j];
				if (j != m - 1) cout << " ";
				else cout << endl;
			}
		}
	}
	return 0;
}

c124: 00532 - Dungeon Master

解題心得

除了東西南北外，多考慮上下的bfs。

程式碼

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

struct Point
{
	int level, x, y, step = -1;
};
int l, r, c;
char map[31][31][31];


int main()
{
	
	while (cin >> l >> r >> c)
	{
		if (l == 0 && r == 0 && c == 0) break;

		bool isVisit[31][31][31] = { false };
		Point start, end, now;
		for (int i = 0; i < l; i++)
		{
			for (int j = 0; j < r; j++)
			{
				for (int k = 0; k < c; k++)
				{
					cin >> map[i][j][k];
					if (map[i][j][k] == 'S')
						start.level = i, start.x = j, start.y = k;
					if (map[i][j][k] == 'E')
						end.level = i, end.x = j, end.y = k;
				}
			}
			cin.ignore();
		}
		
		queue<Point> q;
		start.step = 0;
		q.push(start);
		isVisit[start.level][start.x][start.y] = true;
		bool isValid = false;
		while (!q.empty())
		{
			now = q.front(); q.pop();
			//cout << now.level << " " << now.x << " " << now.y << " " << now.step << endl;
			if (map[now.level][now.x][now.y] == 'E')
			{
				cout << "Escaped in " << now.step << " minute(s)." << endl;
				isValid = true;
				break;
			}
			if (now.x - 1 >= 0 && map[now.level][now.x - 1][now.y] != '#' && !isVisit[now.level][now.x - 1][now.y])
			{
				isVisit[now.level][now.x - 1][now.y] = true;
				Point p; p.level = now.level; p.x = now.x - 1; p.y = now.y;
				p.step = now.step + 1;
				q.push(p);
			}
			if (now.x + 1 < r && map[now.level][now.x + 1][now.y] != '#' && !isVisit[now.level][now.x + 1][now.y])
			{
				isVisit[now.level][now.x + 1][now.y] = true;
				Point p; p.level = now.level; p.x = now.x + 1; p.y = now.y;
				p.step = now.step + 1;
				q.push(p);
			}
			if (now.y - 1 >= 0 && map[now.level][now.x][now.y - 1] != '#' && !isVisit[now.level][now.x][now.y - 1])
			{
				isVisit[now.level][now.x][now.y - 1] = true;
				Point p; p.level = now.level; p.x = now.x; p.y = now.y - 1;
				p.step = now.step + 1;
				q.push(p);
			}
			if (now.y + 1 < c && map[now.level][now.x][now.y + 1] != '#' && !isVisit[now.level][now.x][now.y + 1])
			{
				isVisit[now.level][now.x][now.y + 1] = true;
				Point p; p.level = now.level; p.x = now.x; p.y = now.y + 1;
				p.step = now.step + 1;
				q.push(p);
			}
			if (now.level - 1 >= 0 && map[now.level - 1][now.x][now.y] != '#' && !isVisit[now.level - 1][now.x][now.y])
			{
				isVisit[now.level- 1][now.x][now.y ] = true;
				Point p; p.level = now.level - 1; p.x = now.x; p.y = now.y;
				p.step = now.step + 1;
				q.push(p);
			}
			if (now.level + 1 < l && map[now.level + 1][now.x][now.y] != '#' && !isVisit[now.level + 1][now.x][now.y])
			{
				isVisit[now.level + 1][now.x][now.y] = true;
				Point p; p.level = now.level + 1; p.x = now.x; p.y = now.y;
				p.step = now.step + 1;
				q.push(p);
			}
			isVisit[now.level][now.x][now.y] = true;
		}
		if (!isValid) cout << "Trapped!" << endl;
	}
	return 0;
}

d453: 三、最短距離

解題心得

也是中規中矩的bfs(?

記得清空，以及題目input的座標是從1開始。

程式碼

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

struct Point
{
	int x, y, step = -1;
};
char map[101][101] = { 0 };
bool isVisited[101][101] = { false };
int main()
{
	int N, n, m;
	Point start, end, now;
	cin >> N;
	while (N--)
	{
		cin >> n >> m >> start.x >> start.y >> end.x >> end.y;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				cin >> map[i][j];
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				isVisited[i][j] = false;
		start.x -= 1; start.y -= 1; end.x -= 1; end.y -= 1;
		//bfs
		queue<Point> q;
		isVisited[start.x][start.y] = true; start.step = 1;
		bool isValid = false;
		q.push(start);
		while (!q.empty())
		{
			now = q.front(); 
			q.pop();
			//cout << now.x << " " << now.y << " " << now.step << endl;
			if (now.x == end.x && now.y == end.y)
			{
				cout << now.step << endl;
				isValid = true;
				break;
			}
			if (now.x - 1 >= 0 && map[now.x - 1][now.y] == '0' && !isVisited[now.x - 1][now.y])
			{
				Point p; p.x = now.x - 1; p.y = now.y; 
				isVisited[now.x - 1][now.y] = true;
				p.step = now.step + 1;
				q.push(p);
			}
			if (now.x + 1 < n && map[now.x + 1][now.y] == '0' && !isVisited[now.x + 1][now.y])
			{
				Point p; p.x = now.x + 1; p.y = now.y;
				isVisited[now.x + 1][now.y] = true;
				p.step = now.step + 1;
				q.push(p);
			}
			if (now.y - 1 >= 0 && map[now.x][now.y - 1] == '0' && !isVisited[now.x][now.y - 1])
			{
				Point p; p.x = now.x; p.y = now.y - 1;
				isVisited[now.x][now.y - 1] = true;
				p.step = now.step + 1;
				q.push(p);
			}
			if (now.y + 1 < m && map[now.x][now.y + 1] == '0' && !isVisited[now.x][now.y + 1])
			{
				Point p; p.x = now.x; p.y = now.y + 1;
				isVisited[now.x][now.y + 1] = true;
				p.step = now.step + 1;
				q.push(p);
			}
			isVisited[now.x][now.y] = true;
		}
		if (!isValid) cout << 0 << endl;
	}
	return 0;
}

a290: 新手訓練系列 ~ 圖論

解題心得

中規中矩的題目，記得要清空graph再繼續吃新測資。

不過我是看以前上課講義的演算法寫的XD

程式碼

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

int graph[801][801] = { 0 };

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, m, a, b, now;
	while (cin >> n >> m)
	{
		for (int i = 0; i <= n; i++)
			for (int j = 0; j <= n; j++)
				graph[i][j] = 0;
		while (m--)
		{
			cin >> a >> b;
			graph[a][b] = 1;
		}
		cin >> a >> b;

		queue<int> q;
		bool isVisited[801] = { false }, isValid = false;
		q.push(a);
		isVisited[a] = true;
		while (!q.empty())
		{
			now = q.front();
			q.pop();
			for (int i = 1; i <= n; i++)
			{
				if (graph[now][i] == 1 && isVisited[i] == false)
				{
					isVisited[i] = true;
					q.push(i);

					if (i == b)
					{
						isValid = true;
						break;
					}
				}
			}
			isVisited[now] = true;
		}
		if (isValid) cout << "Yes!!!" << endl;
		else cout << "No!!!" << endl;
	}
	return 0;
}

d365: 10336 - Rank the Languages

解題心得

我反而不是卡bfs，而是卡再怎麼輸出好久，最開始是用map紀錄，但要依照value輸出好麻煩。

程式碼

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

int h, w;
void bfs(vector<vector<char>>& map, int x, int y, char c)
{
	map[y][x] = '@';
	if (x - 1 >= 0 && map[y][x - 1] == c) bfs(map, x - 1, y, c);
	if (x + 1 < w && map[y][x + 1] == c) bfs(map, x + 1, y, c);
	if (y - 1 >= 0 && map[y - 1][x] == c) bfs(map, x, y - 1, c);
	if (y + 1 < h && map[y + 1][x] == c) bfs(map, x, y + 1, c);
}


int main()
{
	int n;
	cin >> n;
	for (int round = 1; round <= n; round++)
	{
		cin >> h >> w;
		int dict[26] = { 0 };
		vector<vector<char>> map(h, vector<char>(w, '@'));
		for (int i = 0; i < h; i++)
		{
			for (int j = 0; j < w; j++)
				cin >> map[i][j];
		}
		for (int i = 0; i < h; i++)
		{
			for (int j = 0; j < w; j++)
			{
				if (map[i][j] != '@')
				{
					dict[map[i][j] - 'a']++;
					bfs(map, j, i, map[i][j]);
				}
			}
		}
		cout << "World #" << round << endl;
		int maxCount = 0;
		for (int i = 0; i < 26; i++)
			maxCount = max(maxCount, dict[i]);
		while (maxCount)
		{
			for (int i = 0; i < 26; i++)
			{
				if (maxCount == dict[i])
					cout << char('a' + i) << ": " << dict[i] << endl;
			}
			maxCount--;
		}
	}
	return 0;
}

Uva 10267: Graphical Editor

解題心得

看起來很麻煩，但基本上只要照著題目敘述做就好，最難的部分只有DFS。

程式碼

#include <iostream>
using namespace std;

char table[101][101];
int m, n;

void fill(int x, int y, char c, char currentColor)
{
	if(currentColor==c) return;
	table[y][x]=c;
	
	if(x>=2 && table[y][x-1]==currentColor) fill(x-1,y,c,currentColor);
	if(x<m && table[y][x+1]==currentColor) fill(x+1,y,c,currentColor);
	if(y>=2 && table[y-1][x]==currentColor) fill(x,y-1,c,currentColor);
	if(y<n && table[y+1][x]==currentColor) fill(x,y+1,c,currentColor);
}

int main()
{
	char cmd,c;
	int x1,x2,y1,y2;
	string name,s;
	while(cin>>cmd)
	{
		if(cmd=='I')
		{
			cin>>m>>n;
			for(int i=0;i<=n;i++)
				for(int j=0;j<=m;j++)
					table[i][j]='O';
		}
		else if(cmd=='L')
		{
			cin>>x1>>y1>>c;
			table[y1][x1]=c;
		}
		else if(cmd=='S')
		{
			cin>>name;
			cout<<name<<endl;
			for(int i=1;i<=n;i++)
			{
				for(int j=1;j<=m;j++)
					cout<<table[i][j];
				cout<<endl;
			}
					
		}
		else if(cmd=='F')
		{
			cin>>x1>>y1>>c;
			fill(x1,y1,c,table[y1][x1]);
		}
		else if(cmd=='V')
		{
			cin>>x1>>y1>>y2>>c;
			if(y1>y2) swap(y1,y2);
			for(int i=y1;i<=y2;i++)
				table[i][x1]=c;
		}
		else if(cmd=='H')
		{
			cin>>x1>>x2>>y1>>c;
			if(x1>x2) swap(x1,x2);
			for(int i=x1;i<=x2;i++)
				table[y1][i]=c;
		}
		else if(cmd=='K')
		{
			cin>>x1>>y1>>x2>>y2>>c;
			for(int i=y1;i<=y2;i++)
				for(int j=x1;j<=x2;j++)
					table[i][j]=c;
		}
		else if(cmd=='C')
		{
			for(int i=0;i<101;i++)
				for(int j=0;j<101;j++)
					table[i][j]='O';
		}
		else if(cmd=='X')
			break;
		else
		{
			cin.ignore();
			getline(cin,s);
		}
	}
}

Uva 389: Basically Speaking

解題心得

先把數字轉回十進位，再轉成要求的進位制表示法。

程式碼

#include <iostream>
using namespace std;

int to_decimal(string s, int base)
{
	int ans = 0;
	for (int i = 0; i < s.size(); i++)
	{
		if ('0' <= s[i] && s[i] <= '9')
			ans = ans * base + s[i] - '0';
		else
			ans = ans * base + s[i] - 'A' + 10;
	}
	return ans;
}
string convert(int n, int base)
{
	string s = "";
	while (n > 0)
	{
		int tmp = n % base;
		if (tmp >= 10)
			s = char(tmp - 10 + 'A') + s;
		else
			s = char(tmp + '0') + s;
		n /= base;
	}
	while (s.size() < 7)
		s = "0" + s;
	while (s.size() > 7)
		s = s.erase(0, 1);
	return s;
}

int main()
{
	string origin;
	int origin_base, new_base;
	while (cin >> origin)
	{
		cin.ignore();
		cin >> origin_base >> new_base;
		int decimal = to_decimal(origin, origin_base);
		cout << convert(decimal, new_base) << endl;
	}
	return 0;
}

Uva 458: The Decoder

解題心得

CPE第二題居然比第一題簡單

程式碼

#include <iostream>
using namespace std;

int main()
{
	string s;
	while(cin>>s)
	{
		for(int i=0;i<s.size();i++)
			cout<<char(s[i]-7);
		cout<<endl;
	}
	return 0;
}

Uva 10050: Hartals

解題心得

如果先判斷日期是不是週五週六，反而會超時QQ

程式碼

#include <iostream>
using namespace std;

int main()
{
	int T,n,p,h[101]={0};
	cin>>T;
	while(T--)
	{
		int ans=0;
		cin>>n>>p;
		for(int i=0;i<p;i++)
			cin>>h[i];
		for(int i=1;i<=n;i++)
		{
			for(int j=0;j<p;j++)
			{
				if(i%h[j]==0&&i%7!=0&&i%7!=6)
				{
					ans++;
					break;
				}
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

Uva 11960: Divisor Game

解題心得

原本的想法是用質數篩法建質數表，然後一個個用質因數分解找因數，因為一個數的因數數量就是質因數次方加一的乘積。

例：36 = 2^2 + 3^2，其因數數量為(2+1)*(2+1)=9。背後原因很簡單就不贅述。

不過寫完後發現會TLE，只好放棄。

參考了CPE提供的參考解法，發現解法其實很簡單。首先同樣要建表，這次建的是因數表。何謂因數？就是某數可以整除的數。反過來想，把某數的倍數與自己通通都加一，因為一定能整除。

為了近一步縮短時間，提前建好答案表。答案表紀錄從1~i的範圍內，因數數量最多的是誰。注意若數量相同，也要更新。

講起來很容易，但就是想不到啊。

程式碼

#include <iostream>
using namespace std;

#define SIZE 1000001

int table[SIZE] = { 0 }, ans[SIZE] = { 0 };

int main()
{
	for (int i = 1; i < SIZE; i++)
	{
		for (int j = i; j < SIZE; j += i)
			table[j]++;
	}
	int maxIndex = 1, maxCount = 0;
	for (int i = 1; i < SIZE; i++)
	{
		if (table[i] >= maxCount)
		{
			maxIndex = i;
			maxCount = table[i];
		}
		ans[i] = maxIndex;
	}
	
	int T, n;
	cin >> T;
	while (T--)
	{
		cin >> n;
		cout << ans[n] << endl;
	}
	return 0;
}

Uva 11536: Smallest Sub-Array

解題心得

參考網路解法才寫出來。

這題似乎要用到two pointer的概念的變化題。

先假設用一個queue來記錄所有sequence中1~k數字的index，以及countk紀錄當下蒐集到1~k中的總共幾個數字，跟一個array來記錄i最後出現的位置。

每次遇到1~k數字，就先丟進queue中。接著檢查是否第一次遇到這個數字(有沒有在queue中，也就是有沒有在highlight起來的範圍內)，若沒有，則更新countk。最後，我們要檢查highlight範圍左側是不是要變化了，判斷方法是看範圍內的最左側，若去掉該位置，依然能保有1~k的數字，那就可以放棄，一直重覆到不能為止。

那又要怎麼確保會找到最短長度呢？首先我們知道當countk==k時就是一組解，而我們的解法是從頭到尾掃過一次並且動態更新，那麼只要每次都檢查當前的解是否更小即可。

另外我在比較cpe提供的參考解法與網路其他人解法時，一開始不懂為何countk只要++，不考慮--的情況。這是因為只有一開始才是還沒找到解的狀態，只要一找到符合的解，只會不斷解查是不是要更新邊界，但也會確保始終是保持1~k數字的區間。

程式碼 

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

int seq[1000001] = { 1,2,3 };

int main()
{
	int T;
	cin >> T;
	for (int round = 1; round <= T; round++)
	{
		int n, m, k;
		cin >> n >> m >> k;

		for (int i = 3; i < n; i++)
			seq[i] = (seq[i - 1] + seq[i - 2] + seq[i - 3]) % m + 1;

		queue<int> q;
		int countK = 0, last_pos[101] = { 0 }, ans = 1000001;
		for (int i = 0; i < 101; i++) last_pos[i] = -1;
		for (int i = 0; i < n; i++)
		{
			if (seq[i] <= k)
			{
				q.push(i);
				if (last_pos[seq[i]] == -1) countK++;
				last_pos[seq[i]] = i;

				while (q.front() != last_pos[seq[q.front()]])
					q.pop();
				if (countK == k)
					ans = min(ans, i - q.front() + 1);
			}
		}
		cout << "Case " << round << ": ";
		if (ans == 1000001) cout << "sequence nai" << endl;
		else cout << ans << endl;
	}
	return 0;
}