#include #include #include #define MAX_V 700 #define INF 1000000000 int capacity[MAX_V][MAX_V]; int flow[MAX_V][MAX_V]; int parent[MAX_V]; int queue[MAX_V], front, rear; char map[15][15]; int node_num[15][15]; int dx[] = {-1, 1, -1, 1}; // ←, →, ↖, ↗ int dy[] = {0, 0, -1, -1}; int bfs(int s, int t, int V){ memset(parent, -1, sizeof(parent)); front = rear = 0; queue[rear++] = s; parent[s] = s; while(front < rear){ int u = queue[front++]; for(int v = 0; v < V; v++){ if(capacity[u][v] > flow[u][v] && parent[v] == -1){ parent[v] = u; queue[rear++] = v; if(v == t) return 1; } } } return 0; } int edmonds_karp(int s, int t, int V){ int max_flow = 0; while(bfs(s, t, V)){ int path_flow = INF; for(int v = t; v != s; v = parent[v]){ int u = parent[v]; if(capacity[u][v] - flow[u][v] < path_flow) path_flow = capacity[u][v] - flow[u][v]; } for(int v = t; v != s; v = parent[v]){ int u = parent[v]; flow[u][v] += path_flow; flow[v][u] -= path_flow; } max_flow += path_flow; } return max_flow; } int main(){ int T; scanf("%d", &T); while(T--){ int n, m; scanf("%d %d", &n, &m); memset(capacity, 0, sizeof(capacity)); memset(flow, 0, sizeof(flow)); int total_seat = 0, broken = 0; for(int i = 0; i < n; i++) scanf("%s", map[i]); int node_count = 0; int left_base = 1, right_base = 350; int source = 0, sink = 699; // 좌석 번호 부여 및 카운트 for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ if(map[i][j] == 'x') { broken++; } node_num[i][j] = (j % 2 == 0) ? left_base++ : right_base++; } } // A→B conflict 간선 추가 for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ if(map[i][j] == 'x' || j % 2 != 0) continue; int u = node_num[i][j]; for(int d = 0; d < 4; d++){ int ni = i + dy[d]; int nj = j + dx[d]; if(ni < 0 || ni >= n || nj < 0 || nj >= m) continue; if(map[ni][nj] == 'x') continue; int v = node_num[ni][nj]; capacity[u][v] = 1; } } } // source → Left group for(int i = 1; i < left_base; i++){ capacity[source][i] = 1; } // Right group → sink for(int i = 350; i < right_base; i++){ capacity[i][sink] = 1; } int max_match = edmonds_karp(source, sink, MAX_V); printf("%d\n", n*m - broken - max_match); } return 0; }

제출 #166048

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: