OJ Board

Code: Select all

cut..

Code: Select all

Removed...

Code: Select all

AC-ed
I read the question wrong again.. :( 

Code: Select all

2

aaa
bbb
aab
aba
abb
a
b
*
aab bbb

abc
abd
aaa
aab
abb
*
abb aab
abc abd
aab bbb

Code: Select all

aab abb 1

abb aab 1
abb abb 0
aab abb 1

Code: Select all

4

dip
lip
mad
map
maple
may
pad
pip
pod
pop
sap
sip
slice
slick
spice
stick
stock
*
spice stock
may pod

dip
lip
mad
map
mapl
maple
may
pad
pip
pod
pop
sap
sip
slice
slick
spice
stick
stock
*
spice slick
may mad
map maple
maple map
map map

mapl
maple
mba
mbal
mbale
mbple
*
mba mapl

map
mapl
maple
mba
mbal
mbale
mbp
mbple
*
mba mapl

Code: Select all

spice stock 4
may pod 3

spice slick 2
may mad 1
map maple 2
maple map 2
map map 0

mba mapl 5

mba mapl 3

Code: Select all

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <cmath>

using namespace std;

// #define DEBUG


// some global data
const int MAX_NUM_WORDS = 200;
int G[MAX_NUM_WORDS][MAX_NUM_WORDS];
int visited[200];

// Assume size of both strings is greater than 1
// and that they are the same size 
// and not the same string
bool isDistOneAway(const string& s1, const string& s2)
{
	if(s1 == s2) return false;
	
	int diff = 0;
	int size = min(s1.size(), s2.size());
	for(int i = 0; i < s1.size(); i++)
		if(s1[i] != s2[i])
		{
			diff++;
			if(diff > 1) return false;
		}
	if(s1.size() != s2.size() && diff != 0) return false;
	return true;
}

// start - current node in bfs process
// dest - destination
// level - which level are we on
// size - how many nodes should we concern ourselves with here
int breadthFirstSearch(int start, int dest, int size)
{
	if(start == dest) return 0;
	queue< pair<int, int> > Q;
	Q.push(make_pair(start, 0));
	
	while(!Q.empty())
	{	
		pair<int,int> r = Q.front();
		int id = r.first;
		Q.pop();
		if(id == dest) return r.second;
			
		for(int i = 0; i < size; i++)
			if(G[id][i] == 1)
				if(visited[i] == 0)
				{
					Q.push(make_pair(i, r.second+1));
				}
		visited[id] = 1;
	}
	
	return -1;
}


int main()
{
	int N;
	cin>>N;
	
	int words_used = 0;
	for(int i = 0; i < N; i++)
	{
		if(i != 0) cout<<endl;
		// reset graph, reset as minimal an amout of memory as possible
		for(int x =0; x < 200; x++)
		for(int y =0; y < 200; y++)
			G[x][y] = 0;
			
		words_used = 0;
		// a vector for each word length
		// some of these i.e. 0 and 1 are unused
		vector<int> vec[11];
		map<string, int> int_map;
		vector<string> id_map;
		
		string str;
		
		while(true)
		{
			getline(cin, str);
			if(str == "" || str == "\n")continue;
			if(str == "*") break;
			// we dont care about "" input since it will never
			// be used and hence does not affect results
			int id = id_map.size();
			id_map.push_back(str);
			
			// each string in dictionary guaranteed to be unique
			vec[str.size()].push_back(id);
			int_map[str] = id;
			words_used++;
			
			#ifdef DEBUG
				cout<<"\t\tread : \""<<str<<"\""<<endl;
			#endif
		}
		
		#ifdef DEBUG
			cout<<"the maps: "<<endl;
			for(int i = 0; i < id_map.size(); i++)
			{
				cout<<"vec : "<<id_map[i]<<endl;
				cout<<"map : "<<int_map[id_map[i]]<<endl<<endl;
			}	
			
			cout<<"\t\tabout to create the graph"<<endl;
		#endif
			
		// create the graph
		// same length words
		for(int j = 1; j < 10; j++)
		for(int x = 0; x < (int)(vec[j].size()-1); x++)
		{
			for(int y = x+1; y < (int)vec[j].size(); y++)
			{
				if(isDistOneAway(id_map[vec[j][x]],id_map[vec[j][y]]))
				{
					G[vec[j][x]][vec[j][y]] = 1;
					G[vec[j][y]][vec[j][x]] = 1;
					#ifdef DEBUG
						cout<<"\t\tadded : "<<id_map[vec[j][x]]<<" ---> "<<id_map[vec[j][y]]<<endl;
					#endif
				}
			}
		}
		// now different length words
		for(int j = 1; j < 10-1; j++)
		for(int x = 0; x < (int)(vec[j].size()); x++)
		{
			for(int y = 0; y < (int)vec[j+1].size(); y++)
			{
				string temp = " " + vec[j][x];
				if(isDistOneAway(id_map[vec[j][x]],id_map[vec[j+1][y]])
					|| isDistOneAway(temp, id_map[vec[j+1][y]]))
				{
					G[vec[j][x]][vec[j+1][y]] = 1;
					G[vec[j+1][y]][vec[j][x]] = 1;
					#ifdef DEBUG
						cout<<"\t\tadded : "<<id_map[vec[j][x]]<<" ---> "<<id_map[vec[j+1][y]]<<endl;
					#endif
				}
			}
		}
		#ifdef DEBUG
			cout<<"\t\twords used = "<<words_used<<endl;
		#endif
	
		// read the next line
		while(true)
		{
			if(cin.peek() == '\n') break;
			string word1, word2;
			cin>>word1;
			if(cin.eof()) break;
			cin>>word2;;
		
			#ifdef DEBUG
				cout<<"\t\ttest : "<<word1<<"  and  "<<word2<<endl;
			#endif
			
			if(word1 == word2)
				cout<<word1<<" "<<word2<<" "<<0<<endl;
			else
			{
				// RUN BREADTH FIRST SEARCH
				for(int j = 0; j < 200; j++)
					visited[j] = 0;
				
				
				if(word1.size() != 1 || word2.size() != 1)
				{
					int steps = breadthFirstSearch(int_map[word1], int_map[word2], words_used);
					cout<<word1<<" "<<word2<<" "<<steps<<endl;
				}
				else
					cout<<word1<<" "<<word2<<" "<<1<<endl;	
			}
			if(cin.peek()=='\n')
				cin.ignore(1);
		}
		if(cin.peek()=='\n')
			cin.ignore(1);
	}
	return 0;
}