＜問題＞
①四角形のフィールドとマンハッタン距離が与えられる。
各セルに鳥が入れば「v」、いなければ「.」で表わされる。
②鳥はガチョウかアヒルだがフィールドだけ見てもわからない。
③ガチョウは少なくとも１匹存在する。
④ガチョウとマンハッタン距離以内にある鳥は必ずガチョウになる。
⑤このとき、ガチョウとアヒルの位置について場合の数を返す。
＜関数＞
座標を保管するテンプレート。
queue <pair <int,int > > q;
q.push(make_pair(x,y)); で(x,y)の座標を保管できます。
i=q.front().first; でxを取り出し、
j=q.front().second; でyを取り出せます。
＜考え方＞
あるガチョウとマンハッタン距離以内にある鳥は全てガチョウということは
逆を返すと、あるアヒルとマンハッタン距離以内にある鳥は全てアヒルになる。
つまり、マンハッタン距離にある鳥同士は全てガチョウ、もしくは全てアヒルになるということがわかる。
これがわかれば、
「マンハッタン距離にある鳥の集合の数＊２」が場合の数にあることが導ける。
ただし、それだとガチョウがいない場合が存在するので、最後に１を引く必要がある。
int count(vector<string> field, int dist) {
int h=field.size(),w=field[0].size();
int ans=1,MOD=1000000007;
queue <pair <int, int> > q;
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
if(field[i][j]!='v')continue;
q.push(make_pair(i,j));
field[i][j]='.';
while(!q.empty()){
int x=q.front().first;
int y=q.front().second;
q.pop();
for(int k=0;k<h;k++)
for(int l=0;l<w;l++)
if(field[k][l]=='v' && (abs(k-x)+abs(l-y))<=dist){
q.push(make_pair(k,l));
field[k][l]='.';
}
}
ans*=2;
ans%=MOD;
}
}
return (ans-1)%MOD;
}
①四角形のフィールドとマンハッタン距離が与えられる。
各セルに鳥が入れば「v」、いなければ「.」で表わされる。
②鳥はガチョウかアヒルだがフィールドだけ見てもわからない。
③ガチョウは少なくとも１匹存在する。
④ガチョウとマンハッタン距離以内にある鳥は必ずガチョウになる。
⑤このとき、ガチョウとアヒルの位置について場合の数を返す。
＜関数＞
座標を保管するテンプレート。
queue <pair <int,int > > q;
q.push(make_pair(x,y)); で(x,y)の座標を保管できます。
i=q.front().first; でxを取り出し、
j=q.front().second; でyを取り出せます。
＜考え方＞
あるガチョウとマンハッタン距離以内にある鳥は全てガチョウということは
逆を返すと、あるアヒルとマンハッタン距離以内にある鳥は全てアヒルになる。
つまり、マンハッタン距離にある鳥同士は全てガチョウ、もしくは全てアヒルになるということがわかる。
これがわかれば、
「マンハッタン距離にある鳥の集合の数＊２」が場合の数にあることが導ける。
ただし、それだとガチョウがいない場合が存在するので、最後に１を引く必要がある。
int count(vector<string> field, int dist) {
int h=field.size(),w=field[0].size();
int ans=1,MOD=1000000007;
queue <pair <int, int> > q;
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
if(field[i][j]!='v')continue;
q.push(make_pair(i,j));
field[i][j]='.';
while(!q.empty()){
int x=q.front().first;
int y=q.front().second;
q.pop();
for(int k=0;k<h;k++)
for(int l=0;l<w;l++)
if(field[k][l]=='v' && (abs(k-x)+abs(l-y))<=dist){
q.push(make_pair(k,l));
field[k][l]='.';
}
}
ans*=2;
ans%=MOD;
}
}
return (ans-1)%MOD;
}