题意：同一行或者列的炮台会被射到，求一个位置设炮台使得其炸掉的炮台最多
ac代码：
#include <bits/stdc++.h> #include <stdio.h> #define ff(i,x,y)for(int i=x;i<y+1;i++) #define fs(i,x,y)for(int i=x;i>y-1;i--) #define all(x) x.begin(),x.end() #define Ins(x) inserter(x,x.begin()) using namespace std; int n,m,p[4010],viscol[2010],visrow[2010],mes[4010],dx[4]={0,0,1,-1},dy[4]={1,-1,0,0}; char mp[2010][2010]; vector<int>col[2010],row[2010]; typedef pair<int,int> pii; bool ppan(int x,int y) { if(x>=1&&x<=n&&y>=1&&y<=m) return true; return false; } void bfs(int x,int y) { queue<pii>hu; pii now(x,y); hu.push(now); int sum=(col[now.second].size()+row[now.first].size()); sum--; while(!hu.empty()) { now=hu.front(); hu.pop(); int ne; ff(i,0,col[now.second].size()-1) { ne=col[now.second][i]; if(!visrow[ne]) { visrow[ne]=1; p[ne]=p[x]; ff(j,0,row[ne].size()-1) if(!viscol[row[ne][j]]) sum++; hu.push(pii(ne,now.second)); } } ff(i,0,row[now.first].size()-1) { ne=row[now.first][i]; if(!viscol[ne]) { viscol[ne]=1; p[ne+n]=p[x]; ff(j,0,col[ne].size()-1) if(!visrow[col[ne][j]]) sum++; hu.push(pii(now.first,ne)); } } } mes[p[x]]=sum; } int main() { scanf("%d%d",&n,&m); ff(i,1,n) { p[i]=i; scanf("%s",mp[i]+1); ff(j,1,m) { p[j+n]=j+n; if(mp[i][j]=='+') { col[j].push_back(i); row[i].push_back(j); } } } int res=0,posx,posy,hupan=0; ff(i,1,n) { ff(j,1,m) { if(!viscol[j]&&!visrow[i]&&mp[i][j]=='+') { viscol[j]=1; visrow[i]=1; p[j+n]=p[i]; bfs(i,j); } } } ff(i,1,n) { ff(j,1,m) { int nownum=0; if(mp[i][j]=='.') { if(p[i]==p[j+n]) nownum=mes[p[i]]; else nownum=mes[p[i]]+mes[p[j+n]]; } if(nownum>res) { hupan=1; res=nownum; posx=i; posy=j; } } } if(hupan) printf("%d\n%d %d",res,posx,posy); else printf("0"); return 0; }
关键：visrow viscol 去标记行列，标记每一个点会超时
