牛客小白月赛64

https://ac.nowcoder.com/acm/contest/49244/B

吐槽：首先我真的对自己无语到了极点，就因为写错了一个坐标卡了一个半小时。

问题：此题就是及其简单的贪心的题目，比赛开始没多久，AC了第一题以后就想出来该怎么做了，但是因为写错了一个坐标，每次都是WA。

注意：其次还要注意数据范围，数据范围是1e3，如果用数组来存每个有鱼的点到四个角的坐标的曼哈顿距离，考虑极端情况，全部都有鱼的话点的数量就是1e3乘以1e3=1e6,而四个角到每个点的曼哈顿距离就有4乘以1e6，如果存距离的数组只开1e3就会发生数组越界。

方法一：比赛代码（待优化）

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m;
char g[N][N];
vector<pair<int ,int>> ve;
int dis[N];//第二个错误，数组范围开小了，应该是int dis[4*1000010]

int main()
{
    cin>>n>>m;
    int pos[4][2]={{0,0},
                   {0,m-1},
                   {0,n-1},//错误就在这应该是n-1，0，因为这里表达的是四个角的坐标
                   {n-1,m-1}};//上左，上右，下左，下右
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>g[i][j];
            if(g[i][j]=='#')
                ve.push_back({i,j});
        }
    }
    int t=0;
    for(int i=0;i<ve.size();i++){
        for(int j=0;j<4;j++){
            dis[t++]=abs(ve[i].first-pos[j][0])+abs(ve[i].second-pos[j][1]);
        }
    }
    sort(dis,dis+t,greater<int>());
    cout<<dis[0];
    //for(auto i:ve)cout<<i.first<<' '<<i.second;
    //for(int i:dis)cout<<i<<' ';
    return 0;
}

方法二：其实这题根本就不要用数组，不用存数据，只是需要知道最大值即可，有些题用数组可能会出现内存超出限制MLE，因此及时计算及时判断最大值就可以了。

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
int n,m,ans;
int main()
{
    IOS;
    cin>>n>>m;
    string s[n+10];//使用了字符串类的数组，如果数据范围过大可能普通数组不行
    for(int i=0;i<n;i++)cin>>s[i];
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(s[i][j]=='#'){
                ans=max(ans,i+j);
                ans=max(ans,i+m-1-j);
                ans=max(ans,(n-1-i)+j);
                ans=max(ans,(n-1-i)+(m-1-j));
            }
        }
    }
    cout<<ans<<'\n';
    return 0;
}

方法三：使用字符串类型的vector也可以

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
int n,m,ans;
int main()
{
    IOS;
    cin>>n>>m;
    vector<string> s(n+10);
    for(int i=0;i<n;i++)cin>>s[i];
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(s[i][j]=='#'){
                ans=max(ans,i+j);
                ans=max(ans,i+m-1-j);
                ans=max(ans,(n-1-i)+j);
                ans=max(ans,(n-1-i)+(m-1-j));
            }
        }
    }
    cout<<ans<<'\n';
    return 0;
}

方法四：这种方法使用内存最少，没有使用数组

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
int n,m,ans;
char ch;
int main()
{
    IOS;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>ch;
            if(ch=='#'){
                ans=max(ans,i+j);
                ans=max(ans,i+m-1-j);
                ans=max(ans,(n-1-i)+j);
                ans=max(ans,(n-1-i)+(m-1-j));
            }
        }
    }
    cout<<ans<<'\n';
    return 0;
}