1、POJ1321棋盘问题
Description
在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。
Input
输入含有多组测试数据。
每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。
每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。
Output
对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。
Sample Input
2 1 #. .# 4 4 ...# ..#. .#.. #... -1 -1
Sample Output
2 1
解题思路：
回溯法递归
从第一行开始每一个一个一个试，下一行也是一个一个试。
AC代码。
import java.util.Scanner; /* * poj 1321 */ public class Main{ static char[][] graph; static boolean[] rows; static boolean[] cols; static int n,k,nums = 0,res = 0; public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(true) { n=sc.nextInt(); k=sc.nextInt(); if(n==-1) break; if(n==1) { System.out.println(1); continue; } graph = new char[n][n]; for(int i=0;i<n;i++) { String str = sc.next(); for(int j=0;j<n;j++) { graph[i][j]=str.charAt(j); } } cols=new boolean[n]; next(0); System.out.println(res); res=0; } } public static void next(int row) { if(row==n) return; for(int i=0;i<n;i++) if(graph[row][i]=='#'&&cols[i]==false) { cols[i]=true; nums++; if(k==nums) { res++; } next(row+1); cols[i]=false; nums--; } next(row+1); } }
2、POJ2251 Dungeon Master
Description
You are trapped in a 3D dungeon and need to find the quickest way out! The dungeon is composed of unit cubes which may or may not be filled with rock. It takes one minute to move one unit north, south, east, west, up or down. You cannot move diagonally and the maze is surrounded by solid rock on all sides.
Is an escape possible? If yes, how long will it take?
Is an escape possible? If yes, how long will it take?
Input
The input consists of a number of dungeons. Each dungeon description starts with a line containing three integers L, R and C (all limited to 30 in size).
L is the number of levels making up the dungeon.
R and C are the number of rows and columns making up the plan of each level.
Then there will follow L blocks of R lines each containing C characters. Each character describes one cell of the dungeon. A cell full of rock is indicated by a '#' and empty cells are represented by a '.'. Your starting position is indicated by 'S' and the exit by the letter 'E'. There's a single blank line after each level. Input is terminated by three zeroes for L, R and C.
L is the number of levels making up the dungeon.
R and C are the number of rows and columns making up the plan of each level.
Then there will follow L blocks of R lines each containing C characters. Each character describes one cell of the dungeon. A cell full of rock is indicated by a '#' and empty cells are represented by a '.'. Your starting position is indicated by 'S' and the exit by the letter 'E'. There's a single blank line after each level. Input is terminated by three zeroes for L, R and C.
Output
Each maze generates one line of output. If it is possible to reach the exit, print a line of the form
where x is replaced by the shortest time it takes to escape.
If it is not possible to escape, print the line
Escaped in x minute(s).
where x is replaced by the shortest time it takes to escape.
If it is not possible to escape, print the line
Trapped!
Sample Input
3 4 5 S.... .###. .##.. ###.# ##### ##### ##.## ##... ##### ##### #.### ####E 1 3 3 S## #E# ### 0 0 0
Sample Output
Escaped in 11 minute(s). Trapped!
解题思路：BFS 注意千万在重新调用之前把数据清干净。
import java.util.HashSet; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main{ static int L,R,C,res=-1; static char[][][] graph; static class Node{ int l,r,c; } static Queue<Integer> que = new LinkedList<Integer>(); static HashSet<Integer> hs = new HashSet<Integer>(); public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(true) { L=sc.nextInt(); R=sc.nextInt(); C=sc.nextInt(); if(L==0)break; graph = new char[L][R][C]; for(int i=0;i<L;i++)for(int j=0;j<R;j++) { String str = sc.next(); for(int k=0;k<C;k++) { graph[i][j][k]=str.charAt(k); if(graph[i][j][k]=='S') { hs.add(set(i,j,k)); que.offer(set(i,j,k)); } } } bfs(); res=-1; hs.clear(); que.clear(); } } public static void bfs() { res++; int size = que.size(); if(size==0) { System.out.println("Trapped!"); return; } while(size-->0){ Node node = get(que.poll()); if(graph[node.l][node.r][node.c]=='E') { System.out.println("Escaped in "+res+" minute(s)."); return; } //上 if(node.l!=L-1) { if(graph[node.l+1][node.r][node.c]=='.'&&!hs.contains(set(node.l+1,node.r,node.c))) { hs.add(set(node.l+1,node.r,node.c)); que.offer(set(node.l+1,node.r,node.c)); }else if(graph[node.l+1][node.r][node.c]=='E') { que.offer(set(node.l+1,node.r,node.c)); } } //下 if(node.l!=0) { if(graph[node.l-1][node.r][node.c]=='.'&&!hs.contains(set(node.l-1,node.r,node.c))) { hs.add(set(node.l-1,node.r,node.c)); que.offer(set(node.l-1,node.r,node.c)); }else if(graph[node.l-1][node.r][node.c]=='E') { que.offer(set(node.l-1,node.r,node.c)); } } //左 if(node.r!=0) { if(graph[node.l][node.r-1][node.c]=='.'&&!hs.contains(set(node.l,node.r-1,node.c))) { hs.add(set(node.l,node.r-1,node.c)); que.offer(set(node.l,node.r-1,node.c)); }else if(graph[node.l][node.r-1][node.c]=='E') { que.offer(set(node.l,node.r-1,node.c)); } } //右 if(node.r!=R-1) { if(graph[node.l][node.r+1][node.c]=='.'&&!hs.contains(set(node.l,node.r+1,node.c))) { hs.add(set(node.l,node.r+1,node.c)); que.offer(set(node.l,node.r+1,node.c)); }else if(graph[node.l][node.r+1][node.c]=='E') { que.offer(set(node.l,node.r+1,node.c)); } } //前 if(node.c!=0) { if(graph[node.l][node.r][node.c-1]=='.'&&!hs.contains(set(node.l,node.r,node.c-1))) { hs.add(set(node.l,node.r,node.c-1)); que.offer(set(node.l,node.r,node.c-1)); }else if(graph[node.l][node.r][node.c-1]=='E') { que.offer(set(node.l,node.r,node.c-1)); } } //后 if(node.c!=C-1) { if(graph[node.l][node.r][node.c+1]=='.'&&!hs.contains(set(node.l,node.r,node.c+1))) { hs.add(set(node.l,node.r,node.c+1)); que.offer(set(node.l,node.r,node.c+1)); }else if(graph[node.l][node.r][node.c+1]=='E') { que.offer(set(node.l,node.r,node.c+1)); } } } bfs(); } public static int set(int l,int r,int c) { return l*10000+r*100+c; } public static Node get(int i) { Node node = new Node(); node.l=i/10000; node.r=(i-node.l*10000)/100; node.c=(i-node.l*10000-node.r*100); return node; } }
3、Catch That Cow
Description
Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 ≤ N ≤ 100,000) on a number line and the cow is at a point K (0 ≤ K ≤ 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting.
* Walking: FJ can move from any point X to the points X - 1 or X + 1 in a single minute
* Teleporting: FJ can move from any point X to the point 2 × X in a single minute.
If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?
Input
Line 1: Two space-separated integers: N and K
Output
Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.
Sample Input
5 17
Sample Output
4
Hint
The fastest way for Farmer John to reach the fugitive cow is to move along the following path: 5-10-9-18-17, which takes 4 minutes.
思路：BFS 注意剪枝 否则会报RE 不信的话输入 0 1000000
import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { static int N,K; static int res=-1; static Queue<Integer> que = new LinkedList<Integer>(); static boolean[] vis = new boolean[1000000]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); N=sc.nextInt(); K=sc.nextInt(); que.offer(N); bfs(0); System.out.println(res); } static void bfs(int deep) { int size = que.size(); if(que.contains(K)) { res=deep; return; } while(size-->0) { int P = que.poll(); vis[P]=true; if(P<K) { if(lim(P+1)&&!vis[P+1])que.offer(P+1); if(lim(P*2)&&!vis[P*2])que.offer(P*2); if(lim(P-1)&&!vis[P-1])que.offer(P-1); }else { if(lim(P-1)&&!vis[P-1])que.offer(P-1); } } if(que.size()!=0)bfs(deep+1); } static boolean lim(int A) { if(A>100000||A<0) return false; else return true; } }
3、POJ3279Fliptile
Description
Farmer John knows that an intellectually satisfied cow is a happy cow who will give more milk. He has arranged a brainy activity for cows in which they manipulate an M × N grid (1 ≤ M ≤ 15; 1 ≤ N ≤ 15) of square tiles, each of which is colored black on one side and white on the other side.
As one would guess, when a single white tile is flipped, it changes to black; when a single black tile is flipped, it changes to white. The cows are rewarded when they flip the tiles so that each tile has the white side face up. However, the cows have rather large hooves and when they try to flip a certain tile, they also flip all the adjacent tiles (tiles that share a full edge with the flipped tile). Since the flips are tiring, the cows want to minimize the number of flips they have to make.
Help the cows determine the minimum number of flips required, and the locations to flip to achieve that minimum. If there are multiple ways to achieve the task with the minimum amount of flips, return the one with the least lexicographical ordering in the output when considered as a string. If the task is impossible, print one line with the word "IMPOSSIBLE".
Input
Line 1: Two space-separated integers: M and N
Lines 2..M+1: Line i+1 describes the colors (left to right) of row i of the grid with N space-separated integers which are 1 for black and 0 for white
Lines 2..M+1: Line i+1 describes the colors (left to right) of row i of the grid with N space-separated integers which are 1 for black and 0 for white
Output
Lines 1..M: Each line contains N space-separated integers, each specifying how many times to flip that particular location.
Sample Input
4 4 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1
Sample Output
0 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0
思路：二进制枚举+自上而下遍历。
WA错误：要求反转次数最小、其次是字典序最小。(MD挂了好些次)
import java.util.Arrays; import java.util.HashMap; import java.util.Scanner; public class Main{ static int[][] graph; static int N, M; public static void main(String[] args) { Scanner sc = new Scanner(System.in); M = sc.nextInt(); N = sc.nextInt(); if (N == 0) return; graph = new int[M][N]; int[][] meijushu = setFirst(); for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { graph[i][j] = sc.nextInt(); } } int MinRes = Integer.MAX_VALUE; HashMap<Integer, int[][]> hm = new HashMap<Integer,int[][]>(); for (int mjs = 0; mjs < meijushu.length; mjs++) {// 枚举数组 int[][] newGraph = new int[M][N]; int[][] res = new int[M][N]; for (int i = 0; i < M; i++) { newGraph[i] = Arrays.copyOf(graph[i], N); } // 第一行下棋 res[0] = Arrays.copyOf(meijushu[mjs], N); for (int i = 0; i < N; i++) { if (meijushu[mjs][i] == 1) chess(newGraph, 0, i); } // 接下来每行下棋 for (int i = 1; i < M; i++) { for (int j = 0; j < N; j++) { if (newGraph[i - 1][j] == 1) { chess(newGraph, i, j); res[i][j] = 1; } } } int sign = 0; for (int i = 0; i < N; i++) { if (newGraph[M - 1][i] == 1) { sign++; break; } } if (sign == 0) { int a = 0; for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { if (1 == res[i][j]) a++; } } if (a < MinRes) { MinRes = a; hm.put(a, res); } } } if (!hm.isEmpty()) { int[][] res = hm.get(MinRes); for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { System.out.print(res[i][j] + " "); } System.out.println(); } return; } System.out.println("IMPOSSIBLE"); } // 二进制枚举数组 public static int[][] setFirst() { int[][] newGraph = new int[(int) Math.pow(2, N)][N]; String str[] = new String[(int) Math.pow(2, N)]; for (int i = 0; i < (int) Math.pow(2, N); i++) { str[i] = Integer.toBinaryString(i); int len = str[i].length(); for (int j = 0; j < N - len; j++) { str[i] = "0" + str[i]; } } for (int i = 0; i < (int) Math.pow(2, N); i++) { for (int j = N - 1; j >= 0; j--) { newGraph[i][j] = str[i].charAt(j) - 48; } /* * for(int j=0;j<N;j++) { System.out.print(newGraph[i][j]+"--"); } * System.out.println(); */ } return newGraph; } // 下棋 public static void chess(int[][] newGraph, int x, int y) { if (newGraph[x][y] == 1) { newGraph[x][y] = 0; } else if (newGraph[x][y] == 0) { newGraph[x][y] = 1; } // 左 if (x > 0) { if (newGraph[x - 1][y] == 1) { newGraph[x - 1][y] = 0; } else if (newGraph[x - 1][y] == 0) { newGraph[x - 1][y] = 1; } } // 上 if (y > 0) { if (newGraph[x][y - 1] == 1) { newGraph[x][y - 1] = 0; } else if (newGraph[x][y - 1] == 0) { newGraph[x][y - 1] = 1; } } // 下 if (y < N - 1) { if (newGraph[x][y + 1] == 1) { newGraph[x][y + 1] = 0; } else if (newGraph[x][y + 1] == 0) { newGraph[x][y + 1] = 1; } } // 右 if (x < M - 1) { if (newGraph[x + 1][y] == 1) { newGraph[x + 1][y] = 0; } else if (newGraph[x + 1][y] == 0) { newGraph[x + 1][y] = 1; } } } }