Несложная задача на поиск в глубину

[FIDE]

Всем привет. Есть несложная(наверняка очень легкая для других) задача на поиск в глубину. http://codeforces.com/problemset/problem/598/D
У меня вот в чем проблема. С одной стороны нужно отмечать пройденные клетки в матрице bool с другой стороны при решение задачи для следующих x,y надо считать что мы никуда не заходили, т.е везде где b[i][j]=true везде должно быть false. Я придумал такой костыль: завел массив пар del и в него кидал все клетки в которые мы заходили, а потом после того как решим задачу для одной пары x,y очищал этот массив. Но такое решение не проходит по времени да и наверняка тут не нужна эта дополнительная память. Подскажите пожалуйста как мне реализовать эту задачу. Спасибо

#include <bits/stdc++.h>
 
using namespace std;

vector <string> a;
vector < vector <bool> > b;
vector < pair<int,int> > del;
int n,m,k,c;

void dfs(const int& x,const int& y)
{
	del.push_back({x,y});
	if (x<0 || y<0 || x>n-1 || y>m-1) return;
	if (b[x][y]) return;
	
	if (a[x][y]=='*')
	{
		c++;
		return;
	}
	b[x][y]=true;
	dfs(x,y-1);
	dfs(x,y+1);
	dfs(x+1,y);
	dfs(x-1,y);
	//b[x][y]=false;
}

int main()
{
	//ifstream cin("in.txt");
	//ofstream cout("out.txt");
	
	cin>>n>>m>>k;
	a.resize(n);
	for (int i=0;i<n;i++) cin>>a[i];

	b.assign(n,vector<bool>(m,false));
	for (int i=0;i<k;i++)
	{
		int x,y; cin>>x>>y;
		del.clear();
		c=0; dfs(x-1,y-1); 
		cout<<c<<"\n";
		for (int j=0;j<del.size();j++) b.at(del[j].first).at(del[j].second)=false; 	
	}
	
}

[FPaul]

А зачем очищать? Ведь если в этой области уже был поиск, то может быть использовать повторно его результаты? А если поиска в области не было, то зачем очищать?

[Poma][a]

Золотые слова..
И совсем не кошерно тут использовать dfs. Крути bfs c очередью. Сохраняй ответы, чтобы не пересчитывать. Тогда сложность будет - кол-во ячеек (для просчета всего)
Можно даже так и сделать. Пройтись по всем ячейкам (квадрат) и смотреть извествен ли для нее результатам. Если нет - запустить bfs - сохранить этот ответ во всех ячейках области (памяти и времени хватит (вроде. не читал ограничения, а открывать лень)).

А потом за О(1) ответчать

[FIDE]

Золотые слова..

Да, действительно. Странно, что мне не пришла в голову такая идея. Всем спасибо.
З.Ы Почему я не могу Ромахе добавить отзыв никак?