0092 - Square Searching
#include <algorithm> #include <iostream> using namespace std; int dp[1000+1][1000+1]; void Init(int n) { for (int i=0; i<=n; ++i) for (int j=0; j<=n; ++j) dp[i][j]=0; } void Slove(int n) { int answer=0; char field[n+1][n+1]; Init(n); for (int i=1; i<=n; ++i) for (int j=1; j<=n; ++j) cin >> field[i][j]; for (int i=1; i<=n; ++i) for (int j=1; j<=n; ++j) if (field[i][j] == '*') dp[i][j]=0; else { dp[i][j]=min( dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]) )+1; answer=max(answer,dp[i][j]); } cout << answer << endl; } int main(void) { int n; while (cin >> n && n) Slove(n); return 0; }
動的計画法を用いて解いた。
最初、stringで入力してしまっててfield[i][0]も入っていたので何回もWrongAnswer。。 (かなり辛い