#include #include #define MAX_MAP 16 typedef struct { int x; int y; int step; }Pos; int N, M, D; int map[MAX_MAP + 1][MAX_MAP]; int max = 0; int selected[3] = { 0 }; const int dx[3] = { 0,-1,0 }; // 좌 상 우 순서 const int dy[3] = { -1,0,1 }; Pos queue[MAX_MAP * MAX_MAP] = { 0 }; int front = 0, rear = 0; void debug(int temp_map[MAX_MAP][MAX_MAP]) { printf("--map--\n"); for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { printf("%d ", temp_map[i][j]); } printf("\n"); } printf("\n"); } int beRange(Pos cur) { if (cur.x >= 0 && cur.x < N && cur.y >= 0 && cur.y < M) { return 1; } return 0; } int find_target(int temp_map[MAX_MAP][MAX_MAP], Pos del[3], int* idx) { int visited[MAX_MAP][MAX_MAP] = { 0 }; while (front < rear) { Pos cur = queue[front++]; //printf("- cur : %d %d %d\n", cur.x, cur.y, cur.step); if (temp_map[cur.x][cur.y] == 1) { //temp_map[cur.x][cur.y] = 0; del[(*idx)++] = (Pos){ cur.x,cur.y }; //if(selected[0]== 1 && selected[1] == 3 && selected[2] == 4) //debug(temp_map); return 1; } for (int i = 0; i < 3; i++) { Pos new = { cur.x + dx[i], cur.y + dy[i], cur.step + 1 }; if (new.step > D) continue; if (!beRange(new)) continue; if (visited[new.x][new.y]) continue; queue[rear++] = new; visited[new.x][new.y] = 1; } } return 0; } int fight() { int cnt = 0; int temp_map[MAX_MAP][MAX_MAP] = { 0 }; memcpy(temp_map, map, sizeof(temp_map)); while (1) { // 1. check end int ret = 1; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (temp_map[i][j] == 1) ret = 0; } } if (ret) return cnt; // 2. find_target Pos del[3] = { 0 }; int del_cnt = 0; for (int i = 0; i < 3; i++) { front = 0, rear = 0; Pos s = { N, selected[i], 0 }; queue[rear++] = s; find_target(temp_map, del, &del_cnt); } for (int i = 0; i < 3; i++) { Pos d = del[i]; if (temp_map[d.x][d.y] == 1) { temp_map[d.x][d.y] = 0; cnt += 1; } } //printf("cnt : %d\n", cnt); // 3. move for (int i = N - 1; i >= 1; i--) { for (int j = 0; j < M; j++) { temp_map[i][j] = temp_map[i - 1][j]; } } for (int j = 0; j < M; j++) { temp_map[0][j] = 0; } } return -1; } void makecase(int n, int idx) { if (n == 3) { //printf("==fight==\n"); //for (int i = 0; i < 3; i++) printf("%d ", selected[i]); //printf("\n"); int res = fight(); if (res > max) max = res; return; } for (int i = idx; i < M; i++) { selected[n] = i; makecase(n + 1, i + 1); } } int main() { scanf("%d %d %d", &N, &M, &D); for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { scanf("%d", &map[i][j]); } } makecase(0, 0); printf("%d\n", max); return 0; }

제출 #147364

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: