Advertisement
hwanil

Untitled

Feb 2nd, 2018
97
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.57 KB | None | 0 0
  1. #include<stdio.h>
  2. #define INF 987654321;
  3. using namespace std;
  4.  
  5. int Y, X;
  6. int map[505][505];
  7. int dy[] = { -1,1,0,0 };
  8. int dx[] = { 0,0,-1,1 };
  9. int check[505][505];
  10. int ans = -1;
  11. void dfs(int y, int x, int len, int sum) {
  12.    
  13.     if (len == 3) {
  14.    
  15.         if (ans < sum) {
  16.             ans = sum;
  17.        
  18.         }
  19.         return;
  20.     }
  21.     for (int i = 0; i < 4; i++) {
  22.         int nY = y + dy[i];
  23.         int nX = x + dx[i];
  24.         if (nY >= 0 && nY < Y && nX >= 0 && nX < X  && !check[nY][nX]) {
  25.             check[nY][nX] = 1;
  26.             dfs(nY, nX, len + 1, sum + map[nY][nX]);
  27.             check[nY][nX] = 0;
  28.         }
  29.     }
  30. }
  31. int main() {
  32.  
  33.     scanf("%d %d", &Y, &X);
  34.     for (int i = 0; i < Y; i++) {
  35.         for (int j = 0; j < X; j++) {
  36.             scanf("%d", &map[i][j]);
  37.         }
  38.     }
  39.  
  40.     for (int i = 0; i < Y; i++) {
  41.         for (int j = 0; j < X; j++) {
  42.             check[i][j] = 1;
  43.             dfs(i, j,0 ,map[i][j]);
  44.             check[i][j] = 0;
  45.  
  46.            
  47.             int min = INF;
  48.             int ret = 0;
  49.             ret = map[i][j];
  50.             // ㅗ,ㅏ,ㅜ,ㅓ 모양 중 최대값
  51.             int cnt = 0;
  52.             for (int k = 0; k < 4; k++) {
  53.                 int nY = i + dy[k];
  54.                 int nX = j + dx[k];
  55.                 if (nY >= 0 && nY < Y && nX >= 0 && nX < X) {
  56.                     cnt++;
  57.                     ret += map[nY][nX];
  58.                     //날개 중 최소값 저장
  59.                     if (min > map[nY][nX]) {
  60.                         min = map[nY][nX];
  61.                     }
  62.                 }
  63.                
  64.                
  65.             }
  66.             //날개가 4개면
  67.             if (cnt == 4) {
  68.                 //날개 중 최소값 빼준다.
  69.                 ret -= min;
  70.                 //cnt 하나 빼줘서, 날개 3개로 만들어준다
  71.                 cnt-=1;
  72.             }
  73.             //날개 3개면
  74.             if (cnt == 3) {
  75.                 //최대값 갱신
  76.                 if (ans < ret) {
  77.                     ans = ret;
  78.                 }
  79.             }
  80.         }
  81.     }
  82.     printf("%d\n",ans);
  83.     return 0;
  84. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement