题目
题目链接:https://gmoj.net/senior/#main/show/6814
思路
设 \(pos[x]\) 表示与当前连通块相连的颜色 \(x\) 的位置。显然总数不会超过 \(nm\),用 vector 即可。
那么当修改颜色的时候,将这个颜色的所有点计入答案,再将这些点相邻的点扔进 vector 即可。
由于每个点只会找不超过 \(4\) 次,时间复杂度 \(O(nm+Q)\)。
代码
#include <bits/stdc++.h>
#define mp make_pair
using namespace std;
const int N=1010,M=1000010;
const int dx[5]={0,0,0,-1,1},dy[5]={0,-1,1,0,0};
int n,m,Q,ans,a[N][N],vis[N][N];
vector<pair<int,int> > pos[M];
int read()
{
int d=0; char ch=getchar();
while (!isdigit(ch)) ch=getchar();
while (isdigit(ch)) d=(d<<3)+(d<<1)+ch-48,ch=getchar();
return d;
}
void dfs(int x,int y,int col)
{
ans++; vis[x][y]=2;
for (int i=1;i<=4;i++)
{
int xx=x+dx[i],yy=y+dy[i];
if (xx<1 || xx>n || yy<1 || yy>m) continue;
if (!vis[xx][yy] && a[xx][yy]==col) dfs(xx,yy,col);
}
}
int main()
{
freopen("color.in","r",stdin);
freopen("color.out","w",stdout);
n=read(); m=read(); Q=read(); read();
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
a[i][j]=read();
dfs(1,1,a[1][1]);
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (vis[i][j]==2)
for (int k=1;k<=4;k++)
{
int x=i+dx[k],y=j+dy[k];
if (x<1 || x>n || y<1 || y>m) continue;
if (!vis[x][y])
{
pos[a[x][y]].push_back(mp(x,y));
vis[x][y]=1;
}
}
for (int i=1,p;i<=Q;i++)
{
p=read();
for (int j=0;j<pos[p].size();j++)
{
ans++;
int x=pos[p][j].first,y=pos[p][j].second;
vis[x][y]=2;
for (int k=1;k<=4;k++)
{
int xx=x+dx[k],yy=y+dy[k];
if (xx<1 || xx>n || yy<1 || yy>m) continue;
if (!vis[xx][yy])
{
pos[a[xx][yy]].push_back(mp(xx,yy));
vis[xx][yy]=1;
}
}
}
pos[p].clear();
printf("%d\n",ans);
}
return 0;
}