Skip to content

Instantly share code, notes, and snippets.

@sarcilav
Created December 10, 2009 12:17
Show Gist options
  • Save sarcilav/253295 to your computer and use it in GitHub Desktop.
Save sarcilav/253295 to your computer and use it in GitHub Desktop.
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
class WordsGame {
public:
int minimumSwaps(vector <string>, string);
};
int doit(const string & base, string swapme)
{
cerr << "base : "<<base<<" swapme : "<<swapme<<endl;
int ans = 0;
for(int i = 0; i< base.size() ; ++i)
{
if( base[i] == swapme[i]) continue;
int pos = swapme.find(base[i]);
swap(swapme[i],swapme[pos]);
++ans;
cerr << "pos : "<<pos<<" swapme : "<<swapme<<endl;
}
cerr<<"end"<<endl<<endl;
return ans;
}
int WordsGame::minimumSwaps(vector <string> grid, string word)
{
string cw = word,tmp;
sort(cw.begin(), cw.end());
int minswaps = INT_MAX;
for(int i = 0; i<grid.size(); ++i)
{
tmp = grid[i];
sort(tmp.begin(),tmp.end());
if(tmp == cw)
minswaps = min(minswaps, doit(word,grid[i]));
}
string gridji;
for(int j = 0; j<grid.size() ; ++j)
{
gridji = "";
for(int i = 0; i<grid[j].size(); ++i)
gridji += grid[i][j];
tmp = gridji;
cerr<<"tmp : "<<tmp<<endl;
sort(tmp.begin(),tmp.end());
if(tmp == cw)
minswaps = min(minswaps, doit(word,gridji));
}
if( minswaps == INT_MAX) return -1;
return minswaps;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment