TLE while solving KATHTHI - KATHTHI

[yagyank]

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