I am trying to solve the problem http://www.spoj.com/problems/KATHTHI/
I used this post as reference for solution http://codeforces.com/blog/entry/22276
This is my solution which is getting timed out after 10th test case
#include<bits/stdc++.h>
#define ll int
using namespace std;
list<pair<ll,bool> > a[1000001];
main()
{
ll r,c;
char s[1001][1001];
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&r,&c);
bool visited[r*c];
ll wt=0;
pair<ll,bool> temp;
memset(visited,0,sizeof(visited));
list<pair<ll,bool> > queue;
list<pair<ll,bool> >::iterator it;
// visited[0]=1;
temp.first=0;
temp.second=0;
queue.push_back(temp);
temp.first=-1;
temp.second=-1;
queue.push_back(temp);
ll start=0,end=r*c-1;
for(int i=0;i<r;++i)
scanf("%s",&s[i]);
for(int i=0;i<r;++i)
{
for(int j=0;j<c;++j)
{
if(i>0)
{
temp.first=((i-1)*c+j);
if(s[i][j]==s[i-1][j])
temp.second=0;
else
temp.second=1;
a[i*c+j].push_back(temp);
}
if(i<r-1)
{
temp.first=((i+1)*c+j);
if(s[i][j]==s[i+1][j])
temp.second=0;
else
temp.second=1;
a[i*c+j].push_back(temp);
}
if(j>0)
{
temp.first=i*c+(j-1);
if(s[i][j]==s[i][j-1])
temp.second=0;
else
temp.second=1;
a[i*c+j].push_back(temp);
}
if(j<c-1)
{
temp.first=i*c+(j+1);
if(s[i][j]==s[i][j+1])
temp.second=0;
else
temp.second=1;
a[i*c+j].push_back(temp);
}
}
}
/* for(int i=0;i<=end;++i)
{
for(it=a[i].begin();it!=a[i].end();++it)
cout<<(*it).first<<(*it).second<<" ";
cout<<endl;
}*/
//for(it=queue.begin();it!=queue.end();++it)
//cout<<(*it).first<<" ";
int ct=0;
while(!queue.empty())
{
++ct;
// cout<<"Hi\n";
temp=queue.front();
queue.pop_front();
// cout<<temp.first<<endl;
// for(it=queue.begin();it!=queue.end();++it)
// cout<<(*it).first<<" ";
// cout<<endl;
if(temp.first!=-1)
{
// cout<<"hi\n";
if(temp.first==(r*c)-1)
{
// cout<<"hi\n";
// cout<<wt<<endl;
break;
}
else if(!visited[temp.first]){
visited[temp.first]=1;
for(it=a[temp.first].begin();it!=a[temp.first].end();++it)
{
if(!visited[(*it).first])
{
if((*it).second==0)
queue.push_front(*it);
else
queue.push_back(*it);
}
// cout<<queue.front().first<<endl;
}
}
else
continue;
}
else
{
queue.push_back(temp);
++wt;
}
}
printf("%d\n",wt);
for(int i=0;i<r*c;++i)
a[i].clear();
}
}