Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<stdio.h>
- #define INF 987654321;
- using namespace std;
- int Y, X;
- int map[505][505];
- int dy[] = { -1,1,0,0 };
- int dx[] = { 0,0,-1,1 };
- int check[505][505];
- int ans = -1;
- void dfs(int y, int x, int len, int sum) {
- if (len == 3) {
- if (ans < sum) {
- ans = sum;
- }
- return;
- }
- for (int i = 0; i < 4; i++) {
- int nY = y + dy[i];
- int nX = x + dx[i];
- if (nY >= 0 && nY < Y && nX >= 0 && nX < X && !check[nY][nX]) {
- check[nY][nX] = 1;
- dfs(nY, nX, len + 1, sum + map[nY][nX]);
- check[nY][nX] = 0;
- }
- }
- }
- int main() {
- scanf("%d %d", &Y, &X);
- for (int i = 0; i < Y; i++) {
- for (int j = 0; j < X; j++) {
- scanf("%d", &map[i][j]);
- }
- }
- for (int i = 0; i < Y; i++) {
- for (int j = 0; j < X; j++) {
- check[i][j] = 1;
- dfs(i, j,0 ,map[i][j]);
- check[i][j] = 0;
- int min = INF;
- int ret = 0;
- ret = map[i][j];
- // ㅗ,ㅏ,ㅜ,ㅓ 모양 중 최대값
- int cnt = 0;
- for (int k = 0; k < 4; k++) {
- int nY = i + dy[k];
- int nX = j + dx[k];
- if (nY >= 0 && nY < Y && nX >= 0 && nX < X) {
- cnt++;
- ret += map[nY][nX];
- //날개 중 최소값 저장
- if (min > map[nY][nX]) {
- min = map[nY][nX];
- }
- }
- }
- //날개가 4개면
- if (cnt == 4) {
- //날개 중 최소값 빼준다.
- ret -= min;
- //cnt 하나 빼줘서, 날개 3개로 만들어준다
- cnt-=1;
- }
- //날개 3개면
- if (cnt == 3) {
- //최대값 갱신
- if (ans < ret) {
- ans = ret;
- }
- }
- }
- }
- printf("%d\n",ans);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement