點擊查看代碼

#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>
#include<ctime>
using namespace std;

const int N=105;
int a[N][N];
int b[N][N];
int n;

bool check(int k)
{
	for(int x=1;x+k-1<=n;x++){
		for(int y=1;y+k-1<=n;y++){
			bool val=true;
			
			for(int i=y;i<y+k;i++){
				if(b[x+k-1][i]-b[x-1][i]==b[n][i]){
					val=false;
					break;
				}
			}
			if(val) return true;
		}
	}
	
	return false;
}

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];
		}
	}
	 // 獲取當前時間戳
	 int start = clock();
	//沒鑰匙直接退出 
	for(int j=1;j<=n;j++){
        if(b[n][j] == 0){  
            cout << 0 << endl;
            return 0;
        }
    }
	
	int l=0,r=n;
	while(l<r){
		int mid=l+r+1>>1;
		if(check(mid)) l=mid;
		else r=mid-1;
	}
	
	cout<<l<<endl;
	cout<<endl;
	//輸出當前時間段 
	cout << "Time: " << (double)(clock()-start)/CLOCKS_PER_SEC << "s" << endl;
	return 0;
}