結果

問題 No.421 しろくろチョコレート
ユーザー uafr_csuafr_cs
提出日時 2016-09-09 23:52:04
言語 Java21
(openjdk 21)
結果
WA  
実行時間 -
コード長 3,783 bytes
コンパイル時間 3,628 ms
コンパイル使用メモリ 79,868 KB
実行使用メモリ 52,728 KB
最終ジャッジ日時 2024-11-16 18:47:18
合計ジャッジ時間 6,998 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 50 ms
37,008 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 AC 50 ms
37,004 KB
testcase_13 AC 49 ms
36,944 KB
testcase_14 AC 49 ms
36,480 KB
testcase_15 AC 48 ms
36,940 KB
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 AC 47 ms
36,636 KB
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 AC 51 ms
36,640 KB
testcase_24 AC 49 ms
36,736 KB
testcase_25 AC 47 ms
37,100 KB
testcase_26 AC 47 ms
37,024 KB
testcase_27 AC 50 ms
37,136 KB
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 AC 48 ms
37,220 KB
testcase_35 AC 51 ms
37,228 KB
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 WA -
testcase_41 WA -
testcase_42 WA -
testcase_43 WA -
testcase_44 WA -
testcase_45 WA -
testcase_46 WA -
testcase_47 WA -
testcase_48 WA -
testcase_49 WA -
testcase_50 WA -
testcase_51 WA -
testcase_52 WA -
testcase_53 WA -
testcase_54 WA -
testcase_55 WA -
testcase_56 WA -
testcase_57 WA -
testcase_58 WA -
testcase_59 WA -
testcase_60 WA -
testcase_61 WA -
testcase_62 AC 48 ms
37,184 KB
testcase_63 AC 47 ms
36,768 KB
testcase_64 AC 49 ms
37,372 KB
権限があれば一括ダウンロードができます

ソースコード

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 long match = bimatch(adj, is_black, new int[size]);
		final long other = Math.max(0, Math.min(white_count, black_count) - match);
		final long 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