kuangbin特別テーマ簡単検索テーマいくつかのテーマ
39603 ワード
1、POJ 1321碁盤問題
Description
所定の形状の碁盤(形状が不規則である可能性がある)の上に駒を並べ、駒に違いはない.任意の2つの駒を碁盤の中の同じ行または同じ列に置くことができないことを要求する場合は、所定の形状と大きさの碁盤に対して、k個の駒を置くすべての実行可能な配置スキームCをプログラミングして解いてください.
Input
複数セットのテストデータを入力します.
各グループのデータの最初の行は2つの正の整数、n kであり、1つのスペースで区切られ、1つのn*nのマトリクス内に碁盤を記述し、駒を置く数を示す.n <= 8 , k <= n
-1-1の場合は入力が終了します.
次のn行は、各行にn文字を有する碁盤の形状を示す.空白領域を表します(データは余分な空白行や空白列が現れないことを保証します).
Output
各セットのデータに対して、1行の出力が与えられ、配置されたシナリオ数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) {
String str = sc.next();
for(int j=0;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)
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?
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.
Output
Each maze generates one line of output. If it is possible to reach the exit, print a line of the form
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 que = new LinkedList();
static HashSet hs = new HashSet();
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;ifor(int j=0;j) {
String str = sc.next();
for(int k=0;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 17Sample Output
4Hint
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 que = new LinkedList();
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
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 1Sample 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;
HashMapint[][]> hm = new HashMapint[][]>();
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*/
}
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;
}
}
}
}