首页 > 专题系列 > Java解POJ > POJ 3740 Easy Finding [解题报告] Java
2013
11-13

POJ 3740 Easy Finding [解题报告] Java

Easy Finding

问题描述 :

Given a M×N matrix A. Aij ∈ {0, 1} (0 ≤ i < M, 0 ≤ j < N), could you find some rows that let every cloumn contains and only contains one 1.

输入:

There are multiple cases ended by EOF. Test case up to 500.The first line of input is M, N (M ≤ 16, N ≤ 300). The next M lines every line contains N integers separated by space.

输出:

For each test case, if you could find it output “Yes, I found it”, otherwise output “It is impossible” per line.

样例输入:

3 3
0 1 0
0 0 1
1 0 0
4 4
0 0 0 1
1 0 0 0
1 1 0 1
0 1 0 0

样例输出:

Yes, I found it
It is impossible

解题代码:

//* @author 
/**
 * @version 2009/08/28
 * @author sbzlyessit
 */

import java.io.*;
import java.util.*;

public class Main {

    private static BufferedReader   in = new BufferedReader(new InputStreamReader(System.in));
    private static StringTokenizer  st;
    private static int[] matrix = new int[300];

    public static void main(String[] argv) throws Exception {
        int  N, M;
        int  i, j, x;
        boolean found;
        while (in.ready()) {
            N = nextInt();
            M = nextInt();
            Arrays.fill(matrix, 0);
            for (i = 0; i < N; i++)
                for (j = 0; j < M; j++)
                    if (nextInt() == 1)
                        matrix[j] |= 1 <<  i;
            for (found = false, i = (1 <<  N) - 1; !found && i >= 0; i--) {
                for (j = 0; j < M; j++) {
                    x = i & matrix[j];
                    if (x == 0 || x - (x & (-x)) != 0) break;
                }
                if (j == M) {
                    found = true;
                    System.out.println("Yes, I found it");
                }
            }
            if (!found) System.out.println("It is impossible");
        }
    }

    private static int nextInt() throws Exception {
        while (st == null || !st.hasMoreTokens())
            st = new StringTokenizer(in.readLine());
        return Integer.parseInt(st.nextToken());
    }

}

  1. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  2. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢