Juan2012 @ 2024-06-18 19:57:56
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
int n,m,q,w,cs,f[1005][1005],d[1005][1005];
int fx[10]={0,0,1,0,-1};
int fy[10]={0,1,0,-1,0};
char a[1005][1005];
bool x[1005][1005];
void bfs(int x, int y){
queue<PII>q;
q.push({x,y});
f[x][y]=cs;
while(q.size()){
PII t=q.front();
q.pop();
int tx,ty,qx,qy;
qx=t.first,qy=t.second;
for(int i=1;i<=4;i++){
tx=qx+fx[i];
ty=qy+fy[i];
if(tx>=1&&tx<=n&&ty>=1&&ty<=n&&(a[qx][qy]=='1'&&a[tx][ty]=='0'||a[qx][qy]=='0'&&a[tx][ty]=='1')&&f[tx][ty]!=cs){
f[tx][ty]=cs;
q.push({tx,ty});
}
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>a[i][j];
cs=1;
while(m--){
cin>>q>>w;
if(x[q][w]){
cout<<d[q][w]<<endl;
continue;
}
bfs(q,w);
int sl=0;
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(f[i][j]==cs) sl++;
cs++;
x[q][w]=true;
d[q][w]=sl;
cout<<sl<<endl;
}
return 0;
}TLE了4个点,求助dl
by do_it_tomorrow @ 2024-06-18 20:25:42
@Juan2012 屎山代码，需要大力优化。。。
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
int n,m,q,w,cs,f[1005][1005],d[1005][1005];
int fx[10]={0,0,1,0,-1};
int fy[10]={0,1,0,-1,0};
char a[1005][1005];
bool x[1005][1005];
vector<PII> v;
void bfs(int x, int y){
queue<PII>q;
q.push({x,y});
f[x][y]=cs;
while(q.size()){
PII t=q.front();
v.push_back(t);
q.pop();
int tx,ty,qx,qy;
qx=t.first,qy=t.second;
for(int i=1;i<=4;i++){
tx=qx+fx[i];
ty=qy+fy[i];
if(tx>=1&&tx<=n&&ty>=1&&ty<=n&&(a[qx][qy]=='1'&&a[tx][ty]=='0'||a[qx][qy]=='0'&&a[tx][ty]=='1')&&f[tx][ty]!=cs){
f[tx][ty]=cs;
q.push({tx,ty});
}
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>a[i][j];
cs=1;
while(m--){
cin>>q>>w;
if(x[q][w]){
cout<<d[q][w]<<endl;
continue;
}
bfs(q,w);
for(PII i:v){
x[i.first][i.second]=d[i.first][i.second]=v.size();
}
cs++;
// x[q][w]=true;
// d[q][w]=sl;
// cout<<sl<<endl;
cout<<v.size()<<'\n';
v.clear();
}
return 0;
}by ATION001 @ 2024-06-18 20:58:06
这题不优化不TLE才怪
这题可以用连通块的思想优化
代码：
#include<bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
int _x[4]={0,0,-1,1},_y[4]={-1,1,0,0};
int b[1005][1005],sum[100010];
char a[1005][1005];
int n,m;
void dfs(int x,int y,int flag){
if(a[x][y]=='o'||b[x][y]!=-1){
return;
}
sum[flag]++,b[x][y]=flag;
for(int i=0;i<4;i++){
if(a[x+_x[i]][y+_y[i]]!=a[x][y]&&b[x+_x[i]][y+_y[i]]==-1&&a[x+_x[i]][y+_y[i]]!='o')
dfs(x+_x[i],y+_y[i],flag);
}
}
//void bfs(int x,int y,int flag){
// queue<pii>q;
// q.push({x,y});
// sum[flag]++,b[x][y]=flag;
// while(q.size()){
// pii p=q.front();
// q.pop();
// for(int i=0;i<4;i++){
// int dx=p.first+_x[i],dy=p.second+_y[i];
// if(a[dx][dy]=='o'||b[dx][dy]!=-1||a[p.first][p.second]==a[dx][dy]){
// continue;
// }
// sum[flag]++,b[dx][dy]=flag;
// q.push({dx,dy});
// }
// }
//}
int main(){
fill(a[0],a[1005],'o');
fill(b[0],b[1005],-1);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
}
}
for(int i=1,x,y;i<=m;i++){
cin>>x>>y;
if(b[x][y]==-1){
dfs(x,y,i);
}else{
sum[i]=sum[b[x][y]];
}
}
for(int i=1;i<=m;i++){
cout<<sum[i]<<endl;
}
return 0;
}by ATION001 @ 2024-06-18 20:59:02
极为丑陋的代码
by ATION001 @ 2024-06-18 21:00:49
@Juan2012 这个跟你的思路更像
#include<bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
int _x[4]={0,0,-1,1},_y[4]={-1,1,0,0};
int b[1005][1005],sum[100010];
char a[1005][1005];
int n,m;
void bfs(int x,int y,int flag){
queue<pii>q;
q.push({x,y});
sum[flag]++,b[x][y]=flag;
while(q.size()){
pii p=q.front();
q.pop();
for(int i=0;i<4;i++){
int dx=p.first+_x[i],dy=p.second+_y[i];
if(a[dx][dy]=='o'||b[dx][dy]!=-1||a[p.first][p.second]==a[dx][dy]){
continue;
}
sum[flag]++,b[dx][dy]=flag;
q.push({dx,dy});
}
}
}
int main(){
fill(a[0],a[1005],'o');
fill(b[0],b[1005],-1);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
}
}
for(int i=1,x,y;i<=m;i++){
cin>>x>>y;
if(b[x][y]==-1){
bfs(x,y,i);
}else{
sum[i]=sum[b[x][y]];
}
}
for(int i=1;i<=m;i++){
cout<<sum[i]<<endl;
}
return 0;
}by Juan2012 @ 2024-06-18 21:52:04
感谢
by Juan2012 @ 2024-06-19 19:24:39
已过，此贴结