本文共 3656 字，大约阅读时间需要 12 分钟。
【编程题】(满分34分) 这是一个纵横火柴棒游戏。如图[1.jpg]，在3x4的格子中，游戏的双方轮流放置火柴棒。其规则是： 1. 不能放置在已经放置火柴棒的地方（即只能在空格中放置）。 2. 火柴棒的方向只能是竖直或水平放置。 3. 火柴棒不能与其它格子中的火柴“连通”。所谓连通是指两根火柴棒可以连成一条直线，且中间没有其它不同方向的火柴“阻拦”。 例如：图[1.jpg]所示的局面下，可以在C2位置竖直放置（为了方便描述格子位置，图中左、下都添加了标记），但不能水平放置，因为会与A2连通。同样道理，B2，B3，D2此时两种方向都不可以放置。但如果C2竖直放置后，D2就可以水平放置了，因为不再会与A2连通（受到了C2的阻挡）。 4. 游戏双方轮流放置火柴，不可以弃权，也不可以放多根。直到某一方无法继续放置，则该方为负（输的一方）。 游戏开始时可能已经放置了多根火柴。 你的任务是：编写程序，读入初始状态，计算出对自己最有利的放置方法并输出。 如图[1.jpg]的局面表示为： 00-1 -000 0100 即用“0”表示空闲位置，用“1”表示竖直放置，用“-”表示水平放置。 【输入、输出格式要求】 用户先输入整数 n(n<100), 表示接下来将输入 n 种初始局面，每种局面占3行(多个局面间没有空白行)。 程序则输出：每种初始局面情况下计算得出的最佳放置法（行号+列号+放置方式）。 例如：用户输入： 2 0111 -000 -000 1111 ---- 0010 则程序可以输出： 00- 211 不难猜出，输出结果的含义为： 对第一个局面，在第0行第0列水平放置 对第二个局面，在第2行第1列垂直放置 注意： 行号、列号都是从0开始计数的。 对每种局面可能有多个最佳放置方法（解不唯一），只输出一种即可。例如，对第一个局面，001 也是正解；最第二个局面，201也是正解。
*************************割了*******************************************************
目前的思路是这样：
首先写一个方法返回这一步的状态下有多少种可行的走法。然后每种方法都递归到下一步（也就是for+递归的老套路），不断递归的结果是可行的摆法越来越少，当不能再摆的时候，如果已经摆了的次数是奇数，则说明自己赢了
断断续续的从昨晚做到今天中午 才做完 结果可以出来 我这里输出了所有结果 没有处理重复
import java.util.Arrays;import java.util.Iterator;import java.util.Scanner;import java.util.Vector;public class 火柴游戏 { public static char[][] rect = new char[3][4]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); sc.nextLine(); for (int i = 0; i < n; i++) { for (int j = 0; j < 3; j++) { String s = sc.nextLine(); for (int j2 = 0; j2 < s.length(); j2++) { rect[j][j2] = s.charAt(j2); } } f(0,new Vector ());// System.out.println();// for (MyPoint point : getMethod()) {// System.out.println(point.x + " " + point.y + " " + point.pos);// } } } public static void f(int step,Vector record) { Vector m = getMethod(); if (m.size() == 0) { if (step % 2 == 1) { System.out.println(record.get(0).x + " " + record.get(0).y + " " + record.get(0).pos); } return; } else { MyPoint temp = null; for (int i = 0; i < m.size(); i++) { temp = m.get(i); rect[temp.x][temp.y] = temp.pos; record.add(temp); f(step + 1,record); rect[temp.x][temp.y] = '0'; record.remove(record.size() - 1); } } } // 返回放火柴的方法 public static Vector getMethod() { Vector point = new Vector (); for (int i = 0; i < rect.length; i++) { for (int j = 0; j < rect[i].length; j++) { if (rect[i][j] == '0') { for (int pos = 0; pos < 2; pos++) { // 0是- 1是1 // 横着 if (pos == 0) { boolean canRowLeft = true; boolean canRowRight = true; for (int left = j - 1; left >= 0; --left) { if (rect[i][left] == '0') continue; if (rect[i][left] == '-') { canRowLeft = false; break; } else { canRowLeft = true; break; } } if (canRowLeft) { for (int right = j + 1; right < rect[0].length; ++right) { if (rect[i][right] == '0') continue; if (rect[i][right] == '-') { canRowRight = false; break; } else { canRowRight = true; break; } } } if (canRowLeft && canRowRight) { point.add(new MyPoint(i, j, '-')); } } else { // 竖着 boolean canColUp = true; boolean canColDown = true; for (int up = i - 1; up >= 0; --up) { if (rect[up][j] == '0') continue; if (rect[up][j] == '1') { canColUp = false; break; } else { canColUp = true; break; } } if (canColUp) { for (int down = j + 1; down < rect.length; ++down) { if (rect[down][j] == '0') continue; if (rect[down][j] == '1') { canColDown = false; break; } else { canColDown = true; break; } } } if (canColUp && canColDown) { point.add(new MyPoint(i, j, '1')); } } } } } } return point; }}// 返回方法返回的类class MyPoint { int x = 0; int y = 0; char pos = '0'; // 1或- public MyPoint(int x, int y, char pos) { this.x = x; this.y = y; this.pos = pos; }} 转载地址：http://ogyvb.baihongyu.com/