Last active
December 29, 2015 01:59
-
-
Save soulmachine/7597315 to your computer and use it in GitHub Desktop.
Square Detector
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <string> | |
#include <utility> | |
#include <vector> | |
#include <climits> | |
#include <cstdio> | |
using namespace std; | |
bool detect(vector<string> square) { | |
typedef pair<int, int> point_t; | |
const int m = square.size(); | |
const int n = square[0].size(); | |
point_t left_top, right_bottom; | |
// find the first '#' as left top | |
bool left_top_found = false; | |
for (int i = 0; i < m && !left_top_found; ++i) { | |
for (int j = 0; j < n; ++j) { | |
if (square[i][j] == '#') { | |
left_top.first = i; | |
left_top.second = j; | |
left_top_found = true; | |
break; | |
} | |
} | |
} | |
// find right bottom | |
point_t white = make_pair(INT_MAX, INT_MAX); // 记录黑色方阵中,最左上的白点 | |
for (int i = left_top.first; i < m; ++i) { | |
for (int j = 0; j < n; ++j) { | |
if (square[i][j] == '#') { | |
if (j < left_top.second) return false; | |
right_bottom.first = i; | |
right_bottom.second = j; | |
if (white.first <= right_bottom.first && white.second <= right_bottom.second) | |
return false; | |
} | |
else { | |
if (j >= left_top.second && white.first == INT_MAX) { | |
white.first = i; | |
white.second = j; | |
} | |
} | |
} | |
} | |
return right_bottom.first - left_top.first == right_bottom.second - left_top.second; | |
} | |
int main() { | |
freopen("square_detector.txt", "r", stdin); | |
freopen("square_detector_out.txt", "w", stdout); | |
int T; | |
cin >> T; | |
int case_no = 0; | |
while (T-- > 0) { | |
++case_no; | |
int N; | |
cin >> N; | |
vector<string> square; | |
for (int i = 0; i < N; ++i) { | |
string str; | |
cin >> str; | |
square.push_back(str); | |
} | |
if (detect(square)) { | |
cout << "Case #" << case_no << ": YES" << endl; | |
} | |
else { | |
cout << "Case #" << case_no << ": NO" << endl; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment