#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 pos_to_node[15][15]; int dx[] = {-1, 1, -1, 1}; int dy[] = {1, 1, 0, 0}; 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)); memset(pos_to_node, 0, sizeof(pos_to_node)); int id = 1; int left_nodes[200], right_nodes[200]; int left_cnt = 0, right_cnt = 0; for(int i = 0; i < n; i++) scanf("%s", map[i]); // 노드 번호 부여 및 이분 분할 for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ if(map[i][j] == 'x') continue; pos_to_node[i][j] = id++; if(j % 2 == 0) left_nodes[left_cnt++] = pos_to_node[i][j]; else right_nodes[right_cnt++] = pos_to_node[i][j]; } } // conflict 간선 (Left → Right) 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 = pos_to_node[i][j]; for(int d = 0; d < 4; d++){ int ni = i + dy[d], nj = j + dx[d]; if(ni < 0 || ni >= n || nj < 0 || nj >= m) continue; if(map[ni][nj] == 'x') continue; int v = pos_to_node[ni][nj]; capacity[u][v] = 1; } } } // source = 0, sink = 699 for(int i = 0; i < left_cnt; i++) capacity[0][left_nodes[i]] = 1; for(int i = 0; i < right_cnt; i++) capacity[right_nodes[i]][699] = 1; int max_match = edmonds_karp(0, 699, MAX_V); printf("%d\n", id - 1 - max_match); } return 0; }

제출 #166020

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: