题解 P4380 【[USACO18OPEN]Multiplayer Moo】
自古FJ屁事多，他的奶牛屁事也多
给各位带来一个好玩意儿
C++ STL库的
unordered_map!!!
(需包含头文件<unordered_map>)
没错bits都没法用
另外，这是C++11里的玩意儿，如果不支持C++11的孩子还是看看楼上的吧
介绍一下哈。
unordered_map，是无序映射，（离散化的好玩意儿），他和map不同的是，map底层使用红黑平衡树实现，而unordered_map是使用hash（哈希）实现，也就是说，使用unordered_map建立映射的复杂度是……
O(1)!!!
本题可以采用宽搜求解，运用Flood-Fill算法求解两问，思路如下：
第一问比较简单，枚举每一点并进行flood-fill，并且更新最大值，代码如下
int bfs1(int x,int y) {
int ans(0);
queue<node>que;
node t,s;
t=(node) {
x,y
};
mark[x][y]=1;
que.push(t);
while(!que.empty()) {
t=que.front();
que.pop();
ans++;
for(int i=0; i<4; i++) {
s.x=t.x+mv[i][0];
s.y=t.y+mv[i][1];
if(s.x>=1&&s.x<=n&&s.y>=1&&s.y<=n&&!mark[s.x][s.y]&&mp[s.x][s.y]==mp[t.x][t.y]) {//mp[s.x][s.y]==mp[t.x][t.y]是保证下一个点和这个点是同一个数字
mark[s.x][s.y]=1;
que.push(s);
}
}
}
return ans;
}那么第二问怎么解决呢？我们这样子考虑：
对于任意一个点，我们考虑他能否与四周进行组队（开黑），若是可以的话，将他与四周的点进行组队并连接，若四周的点均不是本身（即符合）
两头奶牛占有的领域必须要同时包含队伍中两头奶牛的编号，不能仅仅包含一头。
这个条件，那么进行Flood-Fill，并且记为数字X与数字Y已经结为一队。那么怎么记录呢？
unordered_{}map!!!
注意，在判断是否允许将此点加入队列时，要判断的不仅仅是
还有
代码如下
int bfs2(int x,int y,int x1,int y1) {
memset(mark,0,sizeof(mark));
//printf("%d %d %d %d\n",x,y,x1,y1);
int ans(0);
int used1=mp[x][y],used2=mp[x1][y1];//used1表示自己的数字编号
//used2表示队友的数字编号
queue<node>que;
node t,s;
t=(node) {
x,y
};
mark[x][y]=1;
que.push(t);
while(!que.empty()) {
t=que.front();
que.pop();
//printf("%d %d\n",t.x,t.y);
ans++;
for(int i=0; i<4; i++) {
s.x=t.x+mv[i][0];
s.y=t.y+mv[i][1];
if(s.x>=1&&s.x<=n&&s.y>=1&&s.y<=n&&!mark[s.x][s.y]&&(mp[s.x][s.y]==used1||mp[s.x][s.y]==used2)) {//有了上面的注释，问题就不大了
mark[s.x][s.y]=1;
que.push(s);
}
}
}
return ans;
}完全代码
#include<bits/stdc++.h>
#include<unordered_map>
#define FILE(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
using namespace std;
int n,ans1,ans2;
int mv[4][2]= {{1,0},{-1,0},{0,1},{0,-1}};
int mp[333][333];
bool mark[333][333];
unordered_map<int,unordered_map<int,bool> >mmp;
struct node {
int x;
int y;
};
int bfs1(int x,int y) {
int ans(0);
queue<node>que;
node t,s;
t=(node) {
x,y
};
mark[x][y]=1;
que.push(t);
while(!que.empty()) {
t=que.front();
que.pop();
ans++;
for(int i=0; i<4; i++) {
s.x=t.x+mv[i][0];
s.y=t.y+mv[i][1];
if(s.x>=1&&s.x<=n&&s.y>=1&&s.y<=n&&!mark[s.x][s.y]&&mp[s.x][s.y]==mp[t.x][t.y]) {
mark[s.x][s.y]=1;
que.push(s);
}
}
}
return ans;
}
int bfs2(int x,int y,int x1,int y1) {
memset(mark,0,sizeof(mark));
//printf("%d %d %d %d\n",x,y,x1,y1);
int ans(0);
int used1=mp[x][y],used2=mp[x1][y1];
queue<node>que;
node t,s;
t=(node) {
x,y
};
mark[x][y]=1;
que.push(t);
while(!que.empty()) {
t=que.front();
que.pop();
//printf("%d %d\n",t.x,t.y);
ans++;
for(int i=0; i<4; i++) {
s.x=t.x+mv[i][0];
s.y=t.y+mv[i][1];
if(s.x>=1&&s.x<=n&&s.y>=1&&s.y<=n&&!mark[s.x][s.y]&&(mp[s.x][s.y]==used1||mp[s.x][s.y]==used2)) {
mark[s.x][s.y]=1;
que.push(s);
}
}
}
return ans;
}
int main() {
//FILE("multimoo");
scanf("%d",&n);
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
scanf("%d",mp[i]+j);
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
if(!mark[i][j])
ans1=max(ans1,bfs1(i,j));//第一问的Flood-fill问题都不大吧
printf("%d\n",ans1);
memset(mark,0,sizeof(mark));
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
for(int k=0; k<4; k++) {
int frx=i+mv[k][0];
int fry=j+mv[k][1];//判断周围四个点能否与当前点结成队友(组队开黑)(划掉)
if(frx>=1&&frx<=n&&fry>=1&&fry<=n&&mp[i][j]!=mp[frx][fry]&&!mmp[mp[i][j]][mp[frx][fry]])//mp[i][j]!=mp[frx][fry]即判断mp[i][j]是否与自己组队（我 和 我 自 己 组 队）
ans2=max(ans2,bfs2(i,j,frx,fry)),mmp[mp[i][j]][mp[frx][fry]]=mmp[mp[frx][fry]][mp[i][j]]=1;//mmp记录当前点与周围是否组过队
}
printf("%d\n",ans2);//华丽丽的输出
return 0;
}