自己测没问题,求助。
#include <bits/stdc++.h>
using namespace std;
short mapp[1005][1005];
int n,m = 0;
vector<int> go[1005][1005];
bool vis[1005][1005];
short change[4][2] = {1,0,-1,0,0,1,0,-1};
void init()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
}
void readMap()
{
cin >> n >> m;
char temp;
for(int y = 1;y <= n;y ++)
{
for(int x = 1;x <= n;x ++)
{
scanf("%c",&temp);
mapp[x][y] = temp - '0';
}
scanf("%c",&temp);
}
}
void printMap()
{
for(int y = 1;y <= n;y ++)
{
for(int x = 1;x <= n;x ++)
{
cout << mapp[x][y];
}
cout << endl;
}
}
long long dfs(int x,int y)
{
if(x<1 || x>n || y<1 || y>n)
{
return 0;
}
//cout << "-----------\n";
//cout << "now dfs position:" << x << ' ' << y << endl;
vis[x][y] = true;
long long ret = 0;
for(int i = 0;i < 4;i ++)
{
int newx = x + change[i][0];
int newy = y + change[i][1];
if(!vis[newx][newy] && mapp[x][y]+mapp[newx][newy]==1)
{
vector<int> v;
v.push_back(x);
v.push_back(y);
go[newx][newy] = v;
ret += dfs(newx,newy);
}
}
return ret + 1;
}
string toString(vector<int> v)
{
stringstream s;
for(int i = 0;i < v.size();i ++)
{
s << v[i];
s << ' ';
}
return s.str();
}
long long answer(int x,int y)
{
//cout << "-----------\n";
if(go[x][y].size() == 2)
{
vector<int> father;
father = go[x][y];
//cout << "memorial:now at " << x << ' ' << y << ' ' << "with father value" << toString(father) << endl;
while(father.size() == 2)
{
father = go[father[0]][father[1]];
//cout << "memorial:now at father value" << toString(father) << endl;
}
return father[0];
}
else
{
//cout << "new block:now at " << x << ' ' << y << '\n';
vector<int> father;
int ret = dfs(x,y);
father.push_back(ret);
go[x][y] = father;
return ret;
}
}
int main()
{
init();
readMap();
//printMap();
int a,b;
for(int i = 0;i < m;i ++)
{
cin >> a >> b;
cout << answer(b,a) << endl;
}
return 0;
}