[kuangbin带你飞]专题一 简单搜索

A-棋盘问题

 水题,dfs枚举行和放了第几个就行了

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

 先用筛法将1000以内的素数打表,然后bfs枚举每一位

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];
            }
        }
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java爬坑系列

【Java入门提高篇】Day28 Java容器类详解(十)LinkedHashMap详解

  今天来介绍一下容器类中的另一个哈希表———》LinkedHashMap。这是HashMap的关门弟子,直接继承了HashMap的衣钵,所以拥有HashMap...

912
来自专栏开发之途

Java集合框架源码解析之HashSet

1254
来自专栏xiaoxi666的专栏

【模板小程序】任意长度非负十进制数转化为二进制(java实现)

2214
来自专栏java一日一条

Java 容器&泛型(1):认识容器

容器是Java语言学习中重要的一部分。泥瓦匠我的感觉是刚开始挺难学的,但等你熟悉它,接触多了,也就“顺理成章”地知道了。Java的容器类主要由两个接口派生而出:...

1202
来自专栏用户画像

7.7.5 最佳归并树

文件经过置换-选择排序之后,得到的是长度不等的初始归并段。下面讨论如何组织初始归并段的归并顺序,使I/O访问次数最少。

791
来自专栏武培轩的专栏

Java中Set集合是如何实现添加元素保证不重复的?

Java中Set集合是如何实现添加元素保证不重复的? Set集合是一个无序的不可以重复的集合。今天来看一下为什么不可以重复。 Set是一个接口,最常用的实现类就...

3957
来自专栏计算机视觉与深度学习基础

Leetcode 209 Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minima...

20810
来自专栏weixuqin 的专栏

数据结构学习笔记(线性表)

3085
来自专栏码匠的流水账

聊聊storm nimbus的mkAssignments

storm-2.0.0/storm-server/src/main/java/org/apache/storm/daemon/nimbus/Nimbus.jav...

1242
来自专栏数据结构与算法

2879 堆的判断

2879 堆的判断 时间限制: 1 s 空间限制: 32000 KB 题目等级 : 黄金 Gold 题目描述 Description 堆是一种常用...

3238

扫码关注云+社区

领取腾讯云代金券