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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s