公式
B - Rectangle Detection 解説 by physics0523
一般的な注意
プログラミング言語で文字列を取り扱う際、多くの言語では最初の文字が \(0\) 文字目なので、実装に用いる言語の仕様を把握しておきましょう。
解法1. ありうる \(A,B,C,D\) を全部試す
まずは、愚直な解法を紹介します。効率的な解法は 解法2 にて説明します。
- \(1 \le A \le B \le 10\)
- \(1 \le C \le D \le 10\)
を満たす整数の組 \((A,B,C,D)\) は \(3025(=55 \times 55)\) 通りしかありません。
これら全通りに対して実際に \(S_1\) から \(S_{10}\) まで全てを生成して入力と比較することで、 \(302500\) 回 (の定数倍) 程度の計算でこの問題に正解できます。
実装例(C++):
#include<bits/stdc++.h>
using namespace std;
int main(){
vector<string> s(10);
for(int i=0;i<10;i++){cin >> s[i];}
for(int a=1;a<=10;a++){
for(int b=a;b<=10;b++){
for(int c=1;c<=10;c++){
for(int d=c;d<=10;d++){
vector<string> t(10);
for(int i=1;i<=10;i++){
for(int j=1;j<=10;j++){
if(a<=i && i<=b && c<=j && j<=d){
t[i-1].push_back('#');
}
else{
t[i-1].push_back('.');
}
}
}
if(s==t){
cout << a << " " << b << "\n" << c << " " << d << "\n";
}
}
}
}
}
return 0;
}
解法2. 効率的な解法
生成される文字列は、 #
でできた長方形をちょうど \(1\) つ含みます。ここから、 \(A,B,C,D\) は以下のように特定できます。
- \(A=\) (
#
を含む最も上の行) - \(B=\) (
#
を含む最も下の行) - \(C=\) (
#
を含む最も左の列) - \(D=\) (
#
を含む最も右の列)
#include<bits/stdc++.h>
using namespace std;
int main(){
vector<string> s(10);
for(int i=0;i<10;i++){cin >> s[i];}
int a=1e9,b=-1e9;
int c=1e9,d=-1e9;
for(int i=0;i<10;i++){
for(int j=0;j<10;j++){
if(s[i][j]=='#'){
a=min(a,i+1);
b=max(b,i+1);
c=min(c,j+1);
d=max(d,j+1);
}
}
}
cout << a << " " << b << "\n";
cout << c << " " << d << "\n";
return 0;
}
投稿日時:
最終更新: