[BOJ] 14391. 종이조각

* (0,0) ~ (n-1, m-1) 까지 완전 탐색하면서 백트래킹으로 전수조사를 한다. 

* 방문 표시 된 좌표는 가로로 숫자를 만드는 부분이고, 방문 표시가 안 된 부분은 세로로 숫자를 만드는 부분이다. 

	T
T	T
	T

이렇게 방문표시가 되어있다면 

 

이렇게 방문 표시가 된 부분은 가로로 직사각형을 만들고.

아닌 부분들은 세로로 직사각형을 만든다. 

 

* 이어지는 숫자를 string으로 만들어서 sum에 누적합을 해 준다. 

 

 

 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128

#include <iostream> #include <vector> #include <cstring>   using namespace std; int n, m; char map[5][5]; int dx[2] = {1, 0}, dy[2] = {0, 1}; bool visited[5][5]; int ans = 0; bool chk[5][5]; int max(const int &a, const int &b) {     if (a > b)         return a;     return b; }   void dfs(int x, int y) {       if (x == n)     {         //visited 처리된 것은 가로로         //아닌 것은 세로로 계산한다.           string tmp = "";         int sum = 0;         memset(chk, 0, sizeof(chk));         for (int i = 0; i < n; i++)         {             for (int j = 0; j < m; j++)             {                 if (chk[i][j])                     continue;                 if (visited[i][j])                 {                     chk[i][j] = true;                     //가로로 연속되는 값을 구한다.                     if (j == m - 1)                     {                         sum += map[i][j] - '0';                     }                     else                     {                         tmp = map[i][j];                         int idx = 0;                         for (int k = j + 1; k < m; k++)                         {                             if (visited[i][k] && !chk[i][k])                             {                                 tmp += map[i][k];                                 chk[i][k] = true;                             }                             else                             {                                 idx = k - 1;                                 break;                             }                         }                         sum += stoi(tmp);                         // cout << tmp << '\n';                         j = idx;                     }                 }                 else                 {                     chk[i][j] = true;                     if (i == n - 1)                     {                         sum += map[i][j] - '0';                     }                     else                     {                         tmp = map[i][j];                           for (int k = i + 1; k < n; k++)                         {                             if (!visited[k][j] && !chk[k][j])                             {                                 tmp += map[k][j];                                 chk[k][j] = true;                             }                             else                             {                                 break;                             }                         }                         sum += stoi(tmp);                         // cout << tmp << '\n';                     }                 }             }         }         ans = max(ans, sum);         return;     }     if (y >= m)     {         x++;         y = 0;     }       visited[x][y] = true;     dfs(x, y + 1);     visited[x][y] = false;     dfs(x, y + 1); } int main() {       ios_base::sync_with_stdio(0);     cin.tie(0);       cin >> n >> m;       for (int i = 0; i < n; i++)     {         for (int j = 0; j < m; j++)         {             cin >> map[i][j];         }     }       dfs(0, 0);     cout << ans << '\n';     return 0; }