现在的位置: 首页 > 综合 > 正文

POJ1222

2013年09月01日 ⁄ 综合 ⁄ 共 2660字 ⁄ 字号 小 中 大 ⁄ 评论关闭

题目：http://acm.pku.edu.cn/JudgeOnline/problem?id=1222

 

  1. import java.util.Scanner;
  3. public class Main {
  5.     int times;
  6.     int[][] puzzle;
  7.     static final int length = 6;
  8.     static final int width = 5;
  9.     int[][] arr;
  10.     int temp;
  11.     int req;
  13.     public Main() {
  14.         Scanner scan = new Scanner(System.in);
  15.         times = scan.nextInt();
  16.         for (int t = 0; t < times; t++) {
  17.             puzzle = new int[width][length];
  18.             arr = new int[width][length];
  19.             for (int i = 0; i < width; i++) {
  20.                 for (int j = 0; j < length; j++) {
  21.                     puzzle[i][j] = scan.nextInt();
  22.                 }
  23.             }
  24.             force();
  25.             System.out.println("PUZZLE #" + (t + 1));
  26.             for (int i = 0; i < width; i++) {
  27.                 for (int j = 0; j < length; j++) {
  28.                     System.out.print(arr[i][j] + " ");
  29.                 }
  30.                 System.out.println();
  31.             }
  32.         }
  33.     }
  35.     //穷举第一行数据，推导下面的数据...
  36.     //判断最后一行是否符合要求
  37.     //6列需要最多计算2^6=64次
  38.     public void force() {
  39.         boolean result = false;
  40.         do {
  41.             result = search();
  42.             if (result) {
  43.                 return;
  44.             }
  45.         } while (plus(arr[0], 0));
  46.     }
  48.     public boolean search() {
  49.         for (int i = 1; i < width; i++) {
  50.             for (int j = 0; j < length; j++) {
  51.                 req = puzzle[i - 1][j];
  52.                 temp = 0;
  53.                 if (j - 1 >= 0) {
  54.                     temp += arr[i - 1][j - 1];
  55.                 }
  56.                 if (j + 1 < length) {
  57.                     temp += arr[i - 1][j + 1];
  58.                 }
  59.                 if (i - 2 >= 0) {
  60.                     temp += arr[i - 2][j];
  61.                 }
  62.                 temp += arr[i - 1][j];
  63.                 if (req != (temp % 2)) {
  64.                     arr[i][j] = 1;
  65.                 } else {
  66.                     arr[i][j] = 0;
  67.                 }
  68.             }
  69.         }
  70.         for (int i = 0; i < length; i++) {
  71.             req = puzzle[width - 1][i];
  72.             temp = 0;
  73.             if (i - 1 >= 0) {
  74.                 temp += arr[width - 1][i - 1];
  75.             }
  76.             temp += arr[width - 2][i];
  77.             temp += arr[width - 1][i];
  78.             if (i + 1 < length) {
  79.                 temp += arr[width - 1][i + 1];
  80.             }
  81.             if (req != (temp % 2)) {
  82.                 return false;
  83.             }
  84.         }
  85.         return true;
  86.     }
  88.     public boolean plus(int[] a, int b) {
  89.         if (b == length) {
  90.             return false;
  91.         } else if (a[b] == 0) {
  92.             a[b]++;
  93.             return true;
  94.         } else {
  95.             a[b] = 0;
  96.             return plus(a, ++b);
  97.         }
  98.     }
  100.     public static void main(String[] args) {
  101.         new Main();
  102.     }
  104. }
返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞