結果

問題 No.421 しろくろチョコレート
ユーザー uafr_cs
提出日時 2016-09-09 23:29:21
言語 Java
(openjdk 23)
結果
WA  
実行時間 -
コード長 3,778 bytes
コンパイル時間 2,102 ms
コンパイル使用メモリ 79,612 KB
実行使用メモリ 38,032 KB
最終ジャッジ日時 2024-11-16 18:40:37
合計ジャッジ時間 6,582 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16 WA * 49
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.BufferedReader;
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
	
	public static boolean augment(ArrayList<HashSet<Integer>> adj, int curr, int[] match, boolean[] visited) {
		if(curr < 0){ return true; }
		
		for(final int next : adj.get(curr)){
			if(visited[next]){ continue; }
			
			visited[next] = true;
			if(augment(adj, match[next], match, visited)){
				match[curr] = next;
				match[next] = curr;
				return true;
			}
		}
		
		return false;
	}
	
	// black -> white
	public static int bimatch(ArrayList<HashSet<Integer>> adj, boolean[] is_black, int[] match){
		boolean[] visited = new boolean[adj.size()];
		Arrays.fill(match, -1);
		
		int count = 0;
		for(int curr = 0; curr < adj.size(); curr++){
			if(!is_black[curr]){ continue; }
			
			//System.out.println(curr);
			if(augment(adj, curr, match, visited)){
				count++;
			}
		}
		
		return count;
	}
	
	public static final int[][] move_dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
	
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		
		final int N = sc.nextInt();
		final int M = sc.nextInt();
		char[][] map = new char[N][];
		for(int i = 0; i < N; i++){
			map[i] = sc.next().toCharArray();
		}

		final int size = N * M;
		ArrayList<HashSet<Integer>> adj = new ArrayList<HashSet<Integer>>();
		for(int i = 0; i < size; i++){
			adj.add(new HashSet<Integer>());
		}
		
		boolean[] is_black = new boolean[size];
		int white_count = 0, black_count = 0;
		for(int src_y = 0; src_y < N; src_y++){
			for(int src_x = 0; src_x < M; src_x++){
				final int curr_id = src_y * M + src_x;
				
				is_black[curr_id] = map[src_y][src_x] == 'b';
				if(map[src_y][src_x] == 'b'){
					black_count++;
				}else if(map[src_y][src_x] == 'w'){
					white_count++;
				}
				
				if(!is_black[curr_id]){ continue; }
				
				for(final int[] move : move_dirs){
					final int nxt_x = src_x + move[0];
					final int nxt_y = src_y + move[1];
					
					if(nxt_x < 0 || nxt_x >= M || nxt_y < 0 || nxt_y >= N){
						continue;
					}else if(map[nxt_y][nxt_x] != 'w'){
						continue;
					}
					
					final int next_id = nxt_y * M + nxt_x;
					adj.get(curr_id).add(next_id);
				}
			}
		}
		
		//System.out.println(adj);
		
		final int match = bimatch(adj, is_black, new int[size]);
		final int other = Math.max(0, Math.min(white_count, black_count) - match);
		final int single = Math.max(white_count, black_count) - match - other;
		
		//System.out.println(white_count + " " + black_count);
		//System.out.println(match + " " + other + " " + single);
		
		System.out.println(match * 100 + other * 10 + single);
	}
	
	public static class Scanner implements Closeable {
		private BufferedReader br;
		private StringTokenizer tok;
 
		public Scanner(InputStream is) throws IOException {
			br = new BufferedReader(new InputStreamReader(is));
		}	
 
		private void getLine() throws IOException {
			while (!hasNext()) {
				tok = new StringTokenizer(br.readLine());
			}
		}
 
		private boolean hasNext() {
			return tok != null && tok.hasMoreTokens();
		}
 
		public String next() throws IOException {
			getLine();
			return tok.nextToken();
		}
 
		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
 
		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}
 
		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}
 
		public void close() throws IOException {
			br.close();
		}
	}
}
0