사탕게임

*(0,0)부터 차례대로 순회하면서 동쪽, 남쪽의 사탕들과 자리를 바꾼다. (swap)

*바꾼 상태에서 맵을 쭉 살펴보면서 가장 긴 수열이 나오는지 확인한다. (바뀐 부분이 속한 행과 열만 살펴보게 되면 예외케이스를 처리할 수 없다. 다른 곳에서 예기치 못하게 긴 수열이 나올 수 있기 때문에)

 

 

#include <iostream> #include <vector> #include <queue> #include <cstring> using namespace std; int n; char map[51][51]; int dx[2] = { 1,0 }, dy[2] = { 0,1 }; int cdx[4] = { -1,1,0,0 }, cdy[4] = { 0,0, 1,-1 }; typedef pair<int, int> pp; bool visited[51][51]; int check() { memset(visited, 0, sizeof(visited)); int ret = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { char color = map[i][j]; for (int k = 0; k < 2; k++) { int nx = i; int ny = j; int res = 1; while (nx + dx[k] < n && ny + dy[k] < n && map[nx+dx[k]][ny+dy[k]] == color) { nx += dx[k]; ny += dy[k]; res++; } ret = ret < res ? res : ret; } } } return ret; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> map[i][j]; } } int ans = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < 2; k++) { int nx = i + dx[k]; int ny = j + dy[k]; if (nx >= n || ny >= n) continue; swap(map[i][j], map[nx][ny]); //행 또는 열에 같은 사탕색이 연속되는 길이를 구한다. int res = check(); ans = ans < res ? res : ans; swap(map[i][j], map[nx][ny]); } } } cout << ans << '\n'; return 0; }