点击查看代码
#include<bits/stdc++.h>using namespace std;bool check(int k,int n,const vector<vector<int> >& pos)
{//枚举所有可以作为障碍区的起始位置 for(int r=0;r<=n-k;r++){for(int c=0;c<=n-k;c++){bool val=true;//检查每一扇门for(int j=0;j<n;j++){//没钥匙就直接失败if(pos[j].empty()){val=false;break;} //检查这扇门在障碍区列范围的情况if(c<=j&&j<c+k){bool all_covered=true;for(int i=0;i<pos[j].size();i++){int row=pos[j][i];if(!(r<=row&&row<r+k)){all_covered=false;}}//如果所有位置都被覆盖，则这个位置不可以使用if(all_covered){val=false;break;}}}if(val) return true; }}return false;
}int main()
{int n;cin>>n;vector<vector<int> > g(n,vector<int>(n));vector<vector<int> > pos(n);//读入迷宫并存储钥匙位置 for(int i=0;i<n;i++){for(int j=0;j<n;j++){cin>>g[i][j];if(g[i][j]==1) pos[j].push_back(i);}}int l=0,r=n; while(l<r){int mid=l+r+1>>1;if(check(mid,n,pos)){l=mid;}else r=mid-1;}cout<<l<<endl;}
使用了核心使用了暴力，最后对数据的遍历使用了一步二分减少复杂度（这是一个好习惯，对于100个数据，调用100次函数的计算量是很大的，使用二分能极大减少函数的调用次数，并不是简单的减少了90次计算，而是减少了90次调用，从10O（n……4）变成了，o（n……4）
以及本题使用的暴力逻辑，障碍块问题，用for（for（））遍历障碍块可能出现的每一个位置，然后对于一个给定的k，对每一列检查再使用pos存储的钥匙范围求解，很原始的思维，我希望通过精妙的算法求解
点击查看代码
#include <bits/stdc++.h>
using namespace std;int n;
int a[105][105];
int b[105][105];bool check(int x, int y, int k)
{for(int i = y; i < y + k; i++)if(b[x+k-1][i] - b[x-1][i] >= b[n][i])return false;return true;
}int main()
{cin >> n;for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){cin >> a[i][j];b[i][j] = b[i-1][j] + a[i][j];}}for(int k = n - 1; k > 0; k--)for(int x = 1; x + k - 1 <= n; x++)for(int y = 1; y + k - 1 <= n; y++)if(check(x, y, k)){cout << k << endl;return 0;}cout << 0 << endl;return 0;
}
