@[VinstaG173](/user/59388)
by peaneevall_kalaa @ 2022-10-07 19:15:53
橙或黄不至于，应该有绿
by happybob @ 2022-10-07 19:23:17
@[happybob](/user/332914) 这题直接暴力枚举墙的位置，再开个O2就可以AC，大佬是不是想得太复杂了？
AC代码如下：
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,a[51][51],dx[]={0,-1,0,1},dy[]={-1,0,1,0},_a,b,c,maxs;
bool vis[51][51];
struct node{
int x,y;
};
int bfs(int x,int y){
vis[x][y]=1;
queue<node> qt;
qt.push({x,y});
int s=0;
while(!qt.empty()){
node now=qt.front();
s++;
for(int i=0;i<4;i++){
if((a[now.x][now.y]>>i)&1) continue;
int nx=now.x+dx[i],ny=now.y+dy[i];
if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&!vis[nx][ny]){
vis[nx][ny]=1;
qt.push({nx,ny});
}
}
qt.pop();
}
return s;
}
pair<int,int> ans(){
pair<int,int> pr;
memset(vis,0,sizeof(vis));
int s=0,maxs=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(!vis[i][j]){
s++;
int t=bfs(i,j);
maxs=max(maxs,t);
}
}
}
pr.first=s;
pr.second=maxs;
return pr;
}
int main(){
scanf("%d%d",&n,&m);
swap(n,m);
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]);
pair<int,int> pr;
pr=ans();
maxs=pr.second;
printf("%d\n%d\n",pr.first,pr.second);
for(int j=1;j<=m;j++){
for(int i=n;i>=1;i--){
for(int k=1;k<=2;k++){
if((a[i][j]>>k)&1){
int nx=i+dx[k],ny=j+dy[k];
if(nx>=1&&nx<=n&&ny>=1&&ny<=m){
a[i][j]-=(1<<k);
int p;
if(k==1) p=3;
else p=0;
a[nx][ny]-=(1<<p);
int t=ans().second;
if(t>maxs){
_a=i;
b=j;
c=k;
maxs=t;
}
a[i][j]+=(1<<k);
a[nx][ny]+=(1<<p);
}
}
}
}
}
printf("%d\n%d %d ",maxs,_a,b);
if(c==1) printf("N");
else printf("E");
return 0;
}
```
by YuRuochen @ 2022-10-07 20:07:09
@[YuRuochen](/user/658786) 开个O2才能AC就代表你的复杂度可能是错误的，我的代码不开也能过
不过说得也对，可能并不是很难
by happybob @ 2022-10-07 20:11:57
@[happybob](/user/332914) 请问大佬有什么办法能不开O2就AC？不是枚举墙吗？
by YuRuochen @ 2022-10-07 20:13:27
@[happybob](/user/332914) 我的时间复杂度为：$O(n^2m^2)$ ，理论上是OK的，就是常数大了一些
by YuRuochen @ 2022-10-07 20:14:36
@[YuRuochen](/user/658786) 给您看一下我的代码吧，复杂度不太清楚，很久以前的了
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 55;
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };
int m, n, a[N][N][5], cnt[N][N], a1, a2, xp, yp, a3 = 0;
bool vis[N][N];
int ap;
pair<int, int> bel[N][N];
void bfs(int x, int y)
{
memset(vis, 0, sizeof vis);
queue<pair<int, int> > q;
q.push(make_pair(x, y));
int cntg = 0;
vis[x][y] = true;
while (q.size())
{
pair<int, int> p = q.front();
q.pop();
cntg++;
bel[p.first][p.second] = make_pair(x, y);
for (int i = 0; i < 4; i++)
{
int nx = p.first + dx[i], ny = p.second + dy[i];
if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && !a[p.first][p.second][i] && !vis[nx][ny])
{
q.push(make_pair(nx, ny));
vis[nx][ny] = true;
}
}
}
cnt[x][y] = cntg;
}
int main()
{
scanf("%d%d", &m, &n);
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
int x;
scanf("%d", &x);
if (x >= 8)
{
x -= 8;
a[i][j][1] = 1;
}
if (x >= 4)
{
x -= 4;
a[i][j][3] = 1;
}
if (x >= 2)
{
x -= 2;
a[i][j][0] = 1;
}
if (x >= 1)
{
x -= 1;
a[i][j][2] = 1;
}
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (!cnt[bel[i][j].first][bel[i][j].second])
{
a1++;
bfs(i, j);
a2 = max(a2, cnt[i][j]);
}
}
}
printf("%d\n%d\n", a1, a2);
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
// 北边
if (a[i][j][0] && i != 1 && bel[i][j] != bel[i + dx[0]][j + dy[0]])
{
int sum = cnt[bel[i][j].first][bel[i][j].second] + cnt[bel[i + dx[0]][j + dy[0]].first][bel[i + dx[0]][j + dy[0]].second];
if (sum > a3)
{
a3 = sum;
xp = i, yp = j;
ap = 0;
}
else if (sum == a3)
{
if (j < yp)
{
xp = i, yp = j;
ap = 0;
}
else if (j == yp)
{
if (i > xp)
{
xp = i, yp = j;
ap = 0;
}
}
}
}
if (a[i][j][3] && j != m && bel[i][j] != bel[i + dx[3]][j + dy[3]])
{
int sum = cnt[bel[i][j].first][bel[i][j].second] + cnt[bel[i + dx[3]][j + dy[3]].first][bel[i + dx[3]][j + dy[3]].second];
if (sum > a3)
{
a3 = sum;
xp = i, yp = j;
ap = 1;
}
else if (sum == a3)
{
if (ap == 1 && j < yp)
{
xp = i, yp = j;
ap = 1;
}
else if (j == yp)
{
if (i > xp && ap == 1)
{
xp = i, yp = j;
ap = 1;
}
}
}
//if (i == 4 && j == 1) printf("%d\n", sum);
}
}
}
printf("%d\n%d %d %s\n", a3, xp, yp, (ap == 0 ? "N" : "E"));
return 0;
}
```
by happybob @ 2022-10-07 20:18:14
@[happybob](/user/332914) 我太懒了，重新做了一遍搜索，其实直接判断可以把复杂度降到 $O(nm)$ 。。。
by YuRuochen @ 2022-10-07 20:21:34
@[YuRuochen](/user/658786) 2. 确实是东边更优。
我枚举每个格子然后先判北面墙再判东面墙（如果你的答案与之前一样或更优那么直接覆盖）然后过了。
<https://www.luogu.com.cn/record/101746018>
by y_kx_b @ 2023-02-09 10:25:46
关于难度评级：
>洛谷早期题库的难度是评出来的，不宜轻易改动
from [this](/discuss/540524)
by y_kx_b @ 2023-02-09 10:32:25