yyc1117 @ 2024-08-22 17:18:34
传送门
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
char s;
int a[1001][1001],n,m,cnt[1001][1001];
bool vis[1001][1001];
const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,0};
void bfs(int x,int y){
queue<PII>q;
q.push({x,y});
vis[x][y]=true;
cnt[x][y]++;
while(q.size()){
PII u=q.front();
q.pop();
for(int i=0;i<4;i++){
int fx=u.first+dx[i],fy=u.second+dy[i];
if(fx<=0 || fx>n || fy<=0 || fy>n || vis[fx][fy] || a[u.first][u.second]==a[fx][fy])continue;
cnt[x][y]++;
vis[fx][fy]=true;
q.push({fx,fy});
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>s;
a[i][j]=s-'0';
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
bfs(i,j);
memset(vis,0,sizeof(vis));
}
}
while(m--){
int b,c;
cin>>b>>c;
cout<<cnt[b][c]<<endl;
}
return 0;
}by yyc1117 @ 2024-08-22 17:20:47
TLE on #1,#3,#9,#10,#11
by wanchenhao @ 2024-08-22 18:01:15
@yyc1117
AC代码求关
#include<bits/stdc++.h>
using namespace std;
int n,m,ans[100002],x,y,f[1002][1002];
char s[1002][1002];
void dfs(int r,int c,int z,int lll){
if (r<0 || r>=n || c<0 || c>=n || f[r][c]!=-1 || s[r][c]-'0'!=z)return;
f[r][c]=lll;ans[lll]++;
dfs(r-1,c,!z,lll);dfs(r+1,c,!z,lll);dfs(r,c-1,!z,lll);dfs(r,c+1,!z,lll);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++){
scanf("%s",s[i]);
}
memset(f,-1,sizeof(f));
for(int i=0;i<m;i++){
scanf("%d%d",&x,&y);x--;y--;
if (f[x][y]==-1)dfs(x,y,s[x][y]-'0',i);
else ans[i]=ans[f[x][y]];
}
for(int i=0;i<m;i++){
cout<<ans[i]<<endl;
}
return 0;
}by wanchenhao @ 2024-08-22 18:01:41
@yyc1117
by yyc1117 @ 2024-08-24 13:36:55
@wanchenhao 谢谢，已关