#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[4] = { 0,0,1,-1 }; const int dy[4] = { -1,1,0,0 }; 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 attack(int temp_map[MAX_MAP][MAX_MAP]) { 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; //debug(temp_map); return 1; } for (int i = 0; i < 4; 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. attack front = 0, rear = 0; for (int i = 0; i < 3; i++) { Pos s = { N, selected[i], 0 }; queue[rear++] = s; cnt += attack(temp_map); //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; }

제출 #147319

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: