[kuangbin带你飞]专题一 简单搜索
A-棋盘问题
import java.util.Scanner;
public class Main {
static int n,k,ans;
static int[][] map;
static boolean[] vis;
static void dfs(int row,int idx) {//row行，已经放了idx个
if(idx == k) {ans++;return;}
for(int i = row;i < n;i++) //行
for(int j = 0;j < n;j++) //列
if(map[i][j] == 0 && !vis[j]) {
vis[j] = true;
dfs(i + 1,idx + 1);
vis[j] = false;
}
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
while(cin.hasNext()) {
ans = 0;
n = cin.nextInt();
k = cin.nextInt();
if(n == -1 && k == -1)
break;
String tmp;
map = new int[n][n];
vis = new boolean[n];
for(int i = 0;i < n;i++) {
tmp = cin.next();
for(int j = 0;j < n;j++)
if(tmp.charAt(j) == '#')
map[i][j] = 0;
else
map[i][j] = 1;
}
dfs(0,0);
System.out.println(ans);
}
}
}B-Dungeon Master
看到最短，最少之类的搜索题，基本都是用bfs，这道题大意是说，给一个三维的迷宫，要从S走到E，问最短走几步。普通的bfs是上下左右四个方向扩展，这个bfs只不过加了往上一层和往下一层，变成了6个方向扩展而已。这里我遇到了一个坑，对象之间赋值不能直接等，还是要用构造方法来初始化，不然会有坑，具体为什么自己好好想想，对象相等，传的是地址，你变他也变了
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class Node {
int x,y,z;
int step;
Node() {}
Node(int z,int y,int x,int step) {
this.z = z;
this.y = y;
this.x = x;
this.step = step;
}
Node(int z,int y,int x) {
this.z = z;
this.y = y;
this.x = x;
}
}
public class Main {
static int high,row,cloum;//高，行，列
static int[][][] map;//0表示能走，1表示不能走
static boolean[][][] vis;
static Queue<Node> q;
static Node start,end;
static int[][] move = {{0,0,1},{0,0,-1},{0,1,0},{0,-1,0},{1,0,0},{-1,0,0}};
static boolean check(int x,int y,int z) {
return x >= 0 && x < cloum && y >= 0 && y < row && z >= 0 && z < high && map[z][y][x] != 1 && !vis[z][y][x];
}
static void bfs() {
Node cur,new_cur;
vis[start.z][start.y][start.x] = true;
q = new LinkedList<Node>();
q.add(start);
while(!q.isEmpty()) {
cur = new Node(q.peek().z,q.peek().y,q.peek().x,q.poll().step);
if(cur.x == end.x && cur.y == end.y && cur.z == end.z) {
System.out.println("Escaped in " + cur.step + " minute(s).");
return;
}
for(int i = 0;i < 6;i++) {
new_cur = new Node(cur.z,cur.y,cur.x,cur.step);
new_cur.x += move[i][0];
new_cur.y += move[i][1];
new_cur.z += move[i][2];
if(check(new_cur.x,new_cur.y,new_cur.z)) {
vis[new_cur.z][new_cur.y][new_cur.x] = true;
new_cur.step++;
q.add(new_cur);
}
}
}
System.out.println("Trapped!");
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
while(cin.hasNext()) {
high = cin.nextInt();
row = cin.nextInt();
cloum = cin.nextInt();
vis = new boolean[high][row][cloum];
if(high == 0)
break;
map = new int[high][row][cloum];
String tmp;
for(int z = 0;z < high;z++) {//高
for(int y = 0;y < row;y++) {//行
tmp = cin.next();
for(int x = 0;x < cloum;x++) {//列
if(tmp.charAt(x) == 'S')
start = new Node(z,y,x,0);
else if(tmp.charAt(x) == 'E')
end = new Node(z,y,x);
else if(tmp.charAt(x) == '#')
map[z][y][x] = 1;
}
}
}
bfs();
}
}
}C-Catch That Cow
这道题，乍一看好像用dfs可以，仔细想想，dfs绝对不行，问题就在于会爆栈，如果你一直递归下去会爆栈的，所以只能用bfs，用一个数组num[i]表示在i位置上用的步数，每次对于一个点x，就去bfsx+1,x-1,x*2，并且把三个情况都入队，然后再扩，直到x=k，这时就返回num[k]-1
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
while(cin.hasNext()) {
int n = cin.nextInt();
int k = cin.nextInt();
int[] num = new int[1<<20];
Queue<Integer> q = new LinkedList<Integer>();
q.add(n);
num[n] = 1;
while(!q.isEmpty()) {
int c = q.poll();
if(c == k) {
System.out.println(num[c] - 1);
break;
}
if(c - 1 >= 0 && num[c - 1] == 0) {
num[c - 1] = num[c] + 1;
q.add(c - 1);
}
if(c + 1 <= 100000 && num[c + 1] == 0) {
num[c + 1] = num[c] + 1;
q.add(c + 1);
}
if(c * 2 <= 100000 && num[c * 2] == 0) {
num[c * 2] = num[c] + 1;
q.add(c * 2);
}
}
}
}
}D-Fliptile
题目大意是说，给一个n*m的网格，1代表黑，0代表白，每次点击一个格子，它和它上下左右共5个格子都会反转，问点击次数最小的方法 除了最后一行，其他任何一行的1都可以通过下一行的翻转转成0，也就是说，除了最后一行，我们总是可以通过翻转，将前n-1行翻转成0，只要按照这样的原则，对于某个位置x，如果它的上一行是0，就翻转它，如果是0，就不翻转。 第一行的翻法直接决定了后面所有的翻法，这就是解决这道题的思路，采用二进制压缩的办法枚举第一行所有可能的翻法，对于样例来说，一行四个数，所以用二进制0000~1111来表示，只要是带1的位置，就要翻转，那么问题来了，如何知道某一位带不带1呢？只要让这个数分别与1000,0100,0010,0001相与，如果结果不是1，说明这一位上不是1
import java.util.*;
public class Main {
final static int N = 16;
static int[][] g = new int[N][N];//待翻转数组
static int[][] t = new int[N][N];//g的副本
static int[][] f = new int[N][N];
static int cnt;//每种方案的翻转次数
static int n,m;//网格大小
static int[][] move = {{0,-1},{0,1},{1,0},{-1,0}};
static void flip(int i,int j) {//翻转
++cnt;//步数加1
f[i][j] = 1;//记录翻转了哪个瓷砖
t[i][j] ^= 1;//首先翻转自己
for(int k = 0;k < 4;k++) //向四个方向寻找，找到就翻转
if(i + move[k][0] > -1 && j + move[k][1] > -1)
t[i + move[k][0]][j + move[k][1]] ^= 1;
}
static boolean ok(int k) {//对于第一行的每一种情况，判断是否能够产生最终的结果
cnt = 0;
for(int i = 0;i < n;i++)
for(int j = 0;j < m;j++)
t[i][j] = g[i][j];
for(int j = 0;j < m;j++)
if((k & (1 << (m - 1 - j))) != 0)//对于k的每一个取值，如1010，找到不为0的列，因为只需要翻转1就可以了
flip(0,j);
for(int i = 1;i < n;i++)//当第一行全部翻转完了，原来为1的位置肯定是0，原来是0的位置肯定是1，这就需要第二行来解决这些为1位置，以此类推
for(int j = 0;j < m;j++)
if(t[i - 1][j] != 0)//如果该列上一个位置是1，那么这个位置需要翻，否则不需要翻
flip(i,j);
for(int j = 0;j < m;j++)//单独考虑最后一行
if(t[n - 1][j] != 0)
return false;
return true;
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
while(cin.hasNext()) {
int p;//记录当前最佳方案第一行的翻转方案
int ans;//记录当前最佳方案的翻转次数
n = cin.nextInt();
m = cin.nextInt();
for(int i = 0;i < n;i++)
for(int j = 0;j < m;j++)
g[i][j] = cin.nextInt();
ans = m * n + 1;p = -1;
for(int i = 0;i < (1 << m);i++) //用来枚举第一行的各种不同翻法，如0001就是只翻最后一个
if(ok(i) && cnt < ans) {//如果找到一种可能并且所用的步数更少的话，记下这种翻法
ans = cnt;
p = i;
}
for(int i = 0;i < n;i++)
for(int j = 0;j < m;j++)
f[i][j] = 0;
if(p >= 0) {//最后找到的就是最少的翻法，模拟一遍，然后输出
ok(p);
for(int i = 0;i < n;i++)
for(int j = 0;j < m;j++)
if(j < m - 1)
System.out.print(f[i][j] + " ");
else
System.out.print(f[i][j] + "\n");
} else
System.out.print("IMPOSSIBLE");
}
}
}E-Find The Multiple
dfs枚举cur*10和cur*10+1即可，long最长的长度是19，所以如果位数大于19就直接return了
import java.util.Scanner;
public class Main {
static int n;
static boolean flag;
static void dfs(int idx,long cur) {//idx当前是几位数，cur当前枚举的数,flag表示找到没有
if(idx > 19 || flag)
return;
if(cur % n == 0) {
flag = true;
System.out.println(cur);
return;
}
dfs(idx + 1,cur * 10);
dfs(idx + 1,cur * 10 + 1);
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
while(cin.hasNext()) {
n = cin.nextInt();
if(n == 0)
break;
flag = false;
dfs(1,1L);
}
}
}F-Prime Path
import java.util.*;
public class Main {
static int start,end;
static TreeSet<Integer> set = new TreeSet<Integer>();
static boolean[] vis;
static boolean check(int a) {
if(a > 1000 && a < 10000 && !set.contains(a) && !vis[a])
return true;
return false;
}
static void bfs() {
Node cur,new_cur;
cur = new Node(start,0);
Queue<Node> q = new LinkedList<Node>();
q.add(cur);
vis[start] = true;
while(!q.isEmpty()) {
new_cur = new Node(q.peek().x,q.poll().step);
if(new_cur.x == end) {
System.out.println(new_cur.step);
return;
}
for(int i = 0;i <= 9;i++) {
cur = new Node(new_cur.x,new_cur.step);
cur.x /= 10;//取出前三位
cur.x = cur.x * 10 + i;//枚举第四位
if(check(cur.x)) {
cur.step++;
q.add(cur);
vis[cur.x] = true;
}
}
for(int i = 0;i <= 9;i++) {
cur = new Node(new_cur.x,new_cur.step);
int a = cur.x % 10;//取出最后一位
cur.x /= 100;//取出前两位
cur.x = cur.x * 100 + i * 10 + a;//枚举第三位
if(check(cur.x)) {
cur.step++;
q.add(cur);
vis[cur.x] = true;
}
}
for(int i = 0;i <= 9;i++) {
cur = new Node(new_cur.x,new_cur.step);
int b = cur.x % 100;//取出最后两位
cur.x /= 1000;//取出第一位
cur.x = cur.x * 1000 + i * 100 + b;//枚举第二位
if(check(cur.x)) {
cur.step++;
q.add(cur);
vis[cur.x] = true;
}
}
for(int i = 1;i <= 9;i++) {
cur = new Node(new_cur.x,new_cur.step);
cur.x %= 1000;//取出第一位
cur.x = cur.x + i * 1000;//枚举第一位
if(check(cur.x)) {
cur.step++;
q.add(cur);
vis[cur.x] = true;
}
}
}
System.out.println("Impossible");
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
//筛法
for(int i = 2;i <= Math.sqrt(10000);i++)
if(!set.contains(i))
for(int j = 2 * i;j < 10000;j += i)
set.add(j);
int n = cin.nextInt();
while((n--) != 0) {
vis = new boolean[10000];
start = cin.nextInt();
end = cin.nextInt();
bfs();
}
}
}
class Node {
int x,step;
Node(int x,int step) {
this.x = x;
this.step = step;
}
}G-Shuffle'm Up
这不算搜索题，应该是模拟题，题目大意是说：已知两堆牌s1和s2的初始状态，其牌数均为c，按给定规则能将他们相互交叉组合成一堆牌s12，再将s12的最底下的c块牌归为s1，最顶的c块牌归为s2，依此循环下去。问s1s2经过多少次洗牌之后，最终能达到状态s12，若永远不可能相同，则输出"-1" 我是这么想的，用一个Set<String>来保存状态，循环模拟，如果找到了和目标一样的排列，就返回答案；如果找到了已经存在于Set中的排列，并且这个排列不是答案的排列，说明出来一个死循环，就直接输出-1
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n = cin.nextInt();
int time = 0;
TreeSet<String> set = new TreeSet<String>();
while((n--) != 0) {
int ans = 0;
set.clear();
int len = cin.nextInt();
char[] res = new char[len * 2];
String s1 = cin.next();
String s2 = cin.next();
String s12 = cin.next();
while(true) {
for(int i = 0;i < 2 * len;i++)
res[i] = (i % 2 == 0) ? s2.charAt(i / 2) : s1.charAt(i / 2);
ans++;
if(s12.equals(new String(res))) {
System.out.println(++time + " " + ans);
break;
}
if(set.contains(new String(res))) {
System.out.println(++time + " " + -1);
break;
}
set.add(new String(res));
s1 = "";
s2 = "";
for(int i = 0;i < len;i++)
s1 = s1 + res[i];
for(int i = len;i < 2 * len;i++)
s2 = s2 + res[i];
}
}
}
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2018-08-26，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
