1. 题目

传送门= ̄ω ̄=

2. 题解

搜索。。。

对于在一个联通块里的点,它们的答案相同。
所以标记不同颜色。
选定一个点,从这个点dfs遍历到的点全部设为一个颜色,并且把这个点设置为该颜色的根节点,并把根节点的答案设置为刚刚dfs遍历到的节点数量。

对于每次查询,我们根据这个点的颜色,找到该颜色的根节点,输出根节点的答案即可。

代码:

#include <bits/stdc++.h>
using namespace std;
bool inb(bool&dig){char c=getchar();while(!isdigit(c))c=getchar();dig=c-'0';}
int n,m,ans[1005][1005],col[1005][1005],ch[1000005],cw[1000005],cnt;
bool mp[1005][1005];
int dfs(int h,int w)
{
    if(h<1||w<1||h>n||w>n)return 0;
    if(col[h][w])return 0;
    if(ans[h][w])return ans[h][w];
    ans[h][w]=1,col[h][w]=cnt;
    if(mp[h][w]^mp[h-1][w])ans[h][w]+=dfs(h-1,w);
    if(mp[h][w]^mp[h+1][w])ans[h][w]+=dfs(h+1,w);
    if(mp[h][w]^mp[h][w-1])ans[h][w]+=dfs(h,w-1);
    if(mp[h][w]^mp[h][w+1])ans[h][w]+=dfs(h,w+1);
    return ans[h][w];
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)inb(mp[i][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(!col[i][j])cnt++,dfs(i,j),ch[cnt]=i,cw[cnt]=j;
    for(int i=1,a,b;i<=m;i++)
        scanf("%d%d",&a,&b),printf("%d\n",ans[ch[col[a][b]]][cw[col[a][b]]]);
    return 0;
}
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *