'알고리즘' 카테고리의 다른 글
| [BS] 백준 6236 용돈 관리 (0) | 2018.04.29 |
|---|---|
| [BS] 백준 2343 기타레슨 (0) | 2018.04.29 |
| [BF] 백준 2775 부녀회장이 될 테야 (0) | 2018.04.29 |
| [DP] 백준 2631 줄세우기 (0) | 2018.04.29 |
| [DP] 백준 5557 1학년 (0) | 2018.04.29 |
[BF] 완전탐색 1018 체스판 다시 칠하기
2018. 4. 29. 00:44
for문 구현
#include <iostream>
#include <algorithm>
using namespace std;
char table[1001][1001];
int find(int starti,int startj)
{
int cnt = 0;//B start
int cnt2 = 0;//W start
for (int i = starti; i < starti+8; ++i) {
for (int j = startj; j < startj + 8; ++j) {
if ((i % 2 == 0 && j % 2 == 0) || (i % 2 != 0 && j % 2 != 0)) {
if (table[i][j] == 'W') {
cnt++;
}
}
if ((i % 2 != 0 && j % 2 == 0) || (i % 2 == 0 && j % 2 != 0)) {
if (table[i][j] == 'B') {
cnt++;
}
}
if ((i % 2 == 0 && j % 2 == 0) || (i % 2 != 0 && j % 2 != 0)) {
if (table[i][j] == 'B') {
cnt2++;
}
}
if ((i % 2 != 0 && j % 2 == 0) || (i % 2 == 0 && j % 2 != 0)) {
if (table[i][j] == 'W') {
cnt2++;
}
}
}
}
return min(cnt, cnt2);
}
int main(void)
{
int n, m;
cin >> n >> m;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> table[i][j];
}
}
int ret = INT32_MAX;
for (int i = 0; i < n - 7; ++i) {
for (int j = 0; j < m - 7; ++j) {
ret = min(ret,find(i, j));
}
}
cout << ret << endl;
return 0;
}
재귀로 구현
#include <iostream>
#include <algorithm>
using namespace std;
char table[1001][1001];
int Bfind(int i, int j,int ans,int sti,int stj) {
//cout << " i : " << i << "j : " << j << " ans : " << ans << " char : " << table[i][j] << '\n';
if (j == stj+8) {
return ans;
}
if (i == sti+8) {
return Bfind(i-8,j+1,ans,sti,stj);
}
if ((i % 2 == 0 && j % 2 == 0) || (i % 2 != 0 && j % 2 != 0)) {
if (table[i][j] == 'W') {
ans++;
}
}
if ((i % 2 != 0 && j % 2 == 0) || (i % 2 == 0 && j % 2 != 0)) {
if (table[i][j] == 'B') {
ans++;
}
}
Bfind(i + 1, j, ans,sti,stj);
}
int Wfind(int i, int j, int ans,int sti,int stj) {
//cout << " i : " << i << "j : " << j << " ans : " << ans << " char : " << table[i][j] << '\n';
if (j == stj+8) {
return ans;
}
if (i == sti+8) {
return Wfind(i - 8, j + 1, ans,sti,stj);
}
if ((i % 2 == 0 && j % 2 == 0) || (i % 2 != 0 && j % 2 != 0)) {
if (table[i][j] == 'B') {
ans++;
}
}
if ((i % 2 != 0 && j % 2 == 0) || (i % 2 == 0 && j % 2 != 0)) {
if (table[i][j] == 'W') {
ans++;
}
}
Wfind(i + 1, j, ans,sti,stj);
}
int find(int starti,int startj)
{
int cnt = 0;//B start
int cnt2 = 0;//W start
cnt = Bfind(starti, startj, 0,starti,startj);
cnt2 = Wfind(starti, startj, 0,starti,startj);
//cout << cnt << ' ' << cnt2 << endl;
return min(cnt, cnt2);
}
int main(void)
{
int n, m;
cin >> n >> m;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> table[i][j];
}
}
int ret = INT32_MAX;
for (int i = 0; i < n - 7; ++i) {
for (int j = 0; j < m - 7; ++j) {
ret = min(ret,find(i, j));
}
}
cout << ret << endl;
return 0;
}