ddd ... dfs??
~~电风扇警告~~
by aminoas @ 2019-05-12 14:10:29
自己中午睡了个觉再看就明白哪里错啦,是记忆化的过程不对
```cpp
#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
vector<vector<int>> arr;
vector<vector<int>> result;
vector<vector<bool>> vist;
vector<int> nums;
int n,m;
int dir[4][2] = {1,0,0,1,-1,0,0,-1};
int step;
int dfs(int x,int y,int color){
vist[x][y] = true;
step++;
for(int i=0;i<4;i++){
int xx = x + dir[i][0];
int yy = y + dir[i][1];
if(xx >= 0 && xx < n && yy >= 0 && yy < n && vist[xx][yy] == false && arr[xx][yy] == !arr[x][y]){
dfs(xx,yy,color);
}
}
result[x][y] = color;
return step;
}
int main(){
cin >> n >>m;
arr = vector<vector<int>>(n,vector<int>(n,0));
result = vector<vector<int>>(n,vector<int>(n,-1));
vist = vector<vector<bool>>(n,vector<bool>(n,false));
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
char t = getchar();
while(t != '1' && t!='0') t = getchar();
arr[i][j] = t - '0';
}
}
vector<int> output;
int color = 0;
for(int i=0;i<m;i++){
int a,b;
cin >> a >> b;
step = 0;
if(!vist[a-1][b-1]){
nums.push_back( dfs(a-1,b-1,color) );
color++;
}
output.push_back(nums[result[a-1][b-1]]);
}
for(auto i : output)
cout << i << endl;
return 0;
}
```
by wzda @ 2019-05-12 14:20:26