글 읽기 - 비숍 질문입니다

woonchoi 1년 전 0

제 머리로는 도저히 반례가 떠오르지 않습니다..

홀수 짝수로 체스판의 흑백을 나누기 위해 2차원 배열을 1차원으로 펼치고 문제를 풀었고

테케와 질문게시판 반례들도 모두 통과합니다..

어떤 반례가 있을까요?..

추가 : 보드의 사이즈가 짝수일 때 흑백 처리를 잘못한걸 확인했습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	static int		n;
	static int[]	map;
	static int		oddMax = 0;
	static int		evenMax = 0;
	public static void main(String[] args) throws Exception
	{
		BufferedReader	br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter	bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder	sb = new StringBuilder();
		StringTokenizer	st;

		n = Integer.parseInt(br.readLine());
		map = new int[n * n];
		for (int y = 0; y < n; y++)
		{
			st = new StringTokenizer(br.readLine());
			for (int x = 0; x < n; x++)
				map[y * n + x] = Integer.parseInt(st.nextToken());
		}
		backtracking(0, 0, 0, 0);
		backtracking(1, 0, 0, 0);
		sb.append(oddMax + evenMax).append('\n');
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}
	
	public static void backtracking(int start, int ur, int ul, int count)
	{
		if (start % 2 == 1)
			oddMax = Math.max(count, oddMax);
		else
			evenMax = Math.max(count, evenMax);
		for (int i = start; i < n * n; i += 2)
		{
			if (map[i] == 1)
			{
				if ((ur & (1 << (i / n + i % n))) != 0 || (ul & (1 << (i / n - i % n + n - 1))) != 0)
					continue ;
				backtracking(i + 2, (ur | (1 << (i / n + i % n))), (ul | (1 << (i / n - i % n + n - 1))), count + 1);
			}
		}
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

비숍 질문입니다

woonchoi 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말