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

H-Pots展开目录

这题就是一个 bfs + 打印路径问题，线 bfs 出答案，然后 dfs 递归打印路径，都是套路了

import java.util.*;

public class Main {
    static String[] num = {"FILL(1)","FILL(2)","DROP(1)","DROP(2)","POUR(1,2)","POUR(2,1)"};
    static int a,b,c;
    static Node[][] v;
    static int bfs(Point t) {
        Queue<Point> q = new LinkedList<Point>();
        v[0][0].step = 1;
        q.add(t);
        while(!q.isEmpty()) {
            Point cur = new Point(q.peek().x,q.poll().y);
            if(cur.x == c || cur.y == c) {
                System.out.println(v[cur.x][cur.y].step - 1);
                dfs(cur.x,cur.y);
                return 0;
            }
            for(int i = 0;i < 6;i++) {
                Point new_cur = new Point(cur.x,cur.y);
                if(i == 0)
                    new_cur.x = a;
                else if(i == 1)
                    new_cur.y = b;
                else if(i == 2)
                    new_cur.x = 0;
                else if(i == 3)
                    new_cur.y = 0;
                else if(i == 4) 
                    if(new_cur.x + new_cur.y <= b) {
                        new_cur.y += new_cur.x;//把A的水全倒进B里
                        new_cur.x = 0;
                    } else {
                        new_cur.x -= (b - new_cur.y);
                        new_cur.y = b;
                    }
                else if(i == 5)
                    if(new_cur.x + new_cur.y <= a) {
                        new_cur.x += new_cur.y;//把B的水全倒进A里
                        new_cur.y = 0;
                    } else {
                        new_cur.y -= (a - new_cur.x);
                        new_cur.x = a;
                    }
                if(v[new_cur.x][new_cur.y].step == 0) {
                    v[new_cur.x][new_cur.y].step = v[cur.x][cur.y].step + 1;
                    v[new_cur.x][new_cur.y].x = cur.x;
                    v[new_cur.x][new_cur.y].y = cur.y;
                    v[new_cur.x][new_cur.y].op = i;
                    q.add(new_cur);
                }
            }
        }
        return -1;
    }
    
    static void dfs(int x,int y) {
        if(x == 0 && y == 0)
            return;
        dfs(v[x][y].x,v[x][y].y);
        System.out.println(num[v[x][y].op]);
    }
    
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        v = new Node[110][110];
        for(int i = 0;i < 110;i++)
            for(int j = 0;j < 110;j++)
                v[i][j] = new Node();
        a = cin.nextInt();
        b = cin.nextInt();
        c = cin.nextInt();
        Point s = new Point(0,0);
        int ans = bfs(s);
        if(ans == -1)
            System.out.println("impossible");
    }
}
class Point {
    int x,y;//x,y分别代表a瓶的水和b瓶的水
    Point(int x,int y) {
        this.x = x;
        this.y = y;
    }
}
class Node {
    int x,y,step,op;//op是用来最后作为num数组的下标指引路径
}

I-Fire Game展开目录

题目大意是说一块地上有草和空地，有两个人想把草烧光，他俩都要在一块地上放火（位置可以相同可以不同，每个人都只能放一次），火可以向四周蔓延，每次蔓延花费 1 分钟，问他俩把这块地稍晚用的最少时间。这道题得思路应该是枚举两个人所有能放火的位置都试一遍，比较得出最短的时间

import java.util.*;

public class Main {
    static int T,n,m;
    static String[] map = new String[11];
    static Node[] node = new Node[122];
    static int[][] move = {{1,0},{-1,0},{0,1},{0,-1}};
    static int[][] vis;//是否烧过
    
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        T = cin.nextInt();
        int t;//草地总共有多少块
        int time = 0;
        while((T--) != 0) {
            t = 0;
            int ans = Integer.MAX_VALUE;
            n = cin.nextInt();
            m = cin.nextInt();
            for(int i = 0;i < 122;i++)//数据范围最大也就11*11
                node[i] = new Node();
            for(int i = 0;i < n;i++) {
                map[i] = cin.next();
                for(int j = 0;j < m;j++) 
                    if(map[i].charAt(j) == '#') {
                        node[t].x = i;
                        node[t].y = j;
                        node[t++].step = 0;
                    }
            }
            for(int i = 0;i < t;i++) {//枚举两个放火位置
                for(int j = i;j < t;j++) {
                    vis = new int[11][11];
                    int cur_ans = bfs(node[i],node[j]);
                    if(cur_ans < ans && judege()) 
                        ans = cur_ans;
                }
            }
            if(ans == Integer.MAX_VALUE)
                System.out.println("Case " + ++time + ": -1");
            else
                System.out.println("Case " + ++time + ": " + ans);
        }
    }
    
    static boolean check(int x,int y) {
        return x >= 0 && x < n && y >= 0 && y < m && vis[x][y] == 0 && map[x].charAt(y) == '#';
    }
    
    static boolean judege() {
        for(int i = 0;i < n;i++)
            for(int j = 0;j < m;j++)
                if(map[i].charAt(j) == '#' && vis[i][j] == 0)//判断有没有烧完
                    return false;
        return true;
    }
    
    static int bfs(Node a,Node b) {
        Queue<Node> q = new LinkedList<Node>();
        q.add(a);q.add(b);
        Node res = new Node();
        vis[a.x][a.y] = vis[b.x][b.y] = 1;//标记烧过
        while(!q.isEmpty()) {
            res = new Node(q.peek().x,q.peek().y,q.poll().step);
            for(int i = 0;i < 4;i++) {
                Node new_cur = new Node(res.x,res.y,res.step);
                new_cur.x += move[i][0];
                new_cur.y += move[i][1];
                if(check(new_cur.x,new_cur.y)) {
                    new_cur.step++;
                    vis[new_cur.x][new_cur.y] = 1;//标记烧过
                    q.add(new_cur);
                }
            }
        }
        return res.step;
    }
}
class Node {
    int x,y,step;
    Node() {}
    Node(int x,int y,int step) {
        this.x = x;
        this.y = y;
        this.step = step;
    }
}

J-Fire!展开目录

题目大意是说，在一个迷宫中 Joe 要从初始位置 'J' 跑出地图（达到边界即可），在他跑出去的同时火 'F' 也在扩散，火烧的方向和 Joe 跑的方向都是上下左右，每秒一格，他必须在火达到之前跑出去，问他是否可以跑出地图，跑出去的最早时间是多少。# 是墙，. 是可行路径，J 是 Joe 的初始位置，F 是火的初始位置。思路是这样的，两次 BFS 分别求火烧到所有可达到位置的最小时间，人走到边界的最少时间，如果移动的时间≥该点着火的时间，则 continue（ps：别被样例误导，火焰可能不止一处）

import java.util.*;

public class Main {
    static final int N = 1005;
    static int n,m;
    static String[] map;//地图
    static Node[] node;
    static int[][] move = {{1,0},{-1,0},{0,1},{0,-1}};
    static int[][] vis;//记录每个点有没有被烧过或者有没有被走过
    static int[][] fire;//记录火烧到点x,y的时间
    
    static void bfs_Fire() {
        vis = new int[N][N];
        Queue<Node> q = new LinkedList<Node>();
        for(int i = 0;i < n;i++)
            for(int j = 0;j < m;j++)
                if(map[i].charAt(j) == 'F') {
                    vis[i][j] = 1;
                    fire[i][j] = 0;
                    q.add(new Node(i,j,0));
                }
        while(!q.isEmpty()) {
            Node cur = new Node(q.peek().x,q.peek().y,q.poll().step);
            for(int i = 0;i < 4;i++) {
                Node new_cur = new Node(cur.x + move[i][0],cur.y + move[i][1],cur.step + 1);
                if(check_Fire(new_cur.x,new_cur.y)) {
                    vis[new_cur.x][new_cur.y] = 1;
                    fire[new_cur.x][new_cur.y] = new_cur.step;
                    q.add(new_cur);
                }
            }
        }
    }
    static int bfs_Joe(int x,int y) {
        vis = new int[N][N];
        Queue<Node> q = new LinkedList<Node>();
        q.add(new Node(x,y,0));
        vis[x][y] = 1;
        while(!q.isEmpty()) {
            Node cur = new Node(q.peek().x,q.peek().y,q.poll().step);
            for(int i = 0;i < 4;i++) {
                Node new_cur = new Node(cur.x + move[i][0],cur.y + move[i][1],cur.step + 1);
                if(new_cur.x < 0 || new_cur.x >= n || new_cur.y < 0 || new_cur.y >= m)//走到边界
                    return new_cur.step;
                if(check_Joe(new_cur)) {
                    vis[new_cur.x][new_cur.y] = 1;
                    q.add(new_cur);
                }
            }
        }
        return 0;
    }
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        while(cin.hasNext()) {
            int j_x = 0,j_y = 0;//Joe的起始坐标
            int f_x = 0,f_y = 0;//火的起始坐标
            fire = new int[N][N];
            map = new String[N];
            node = new Node[N];
            n = cin.nextInt();
            m = cin.nextInt();
            for(int i = 0;i < n;i++) {
                map[i] = cin.next();
                for(int j = 0;j < m;j++) {
                    fire[i][j] = Integer.MAX_VALUE;
                    if(map[i].charAt(j) == 'J') {
                        j_x = i;
                        j_y = j;
                    }
                }
            }
            bfs_Fire();
            int cnt = bfs_Joe(j_x,j_y);
            System.out.println((cnt == 0) ? "IMPOSSIBLE" : cnt);
        }
    }
    
    static boolean check_Fire(int x,int y) {
        return x >= 0 && x < n && y >= 0 && y < m && vis[x][y] != 1 && map[x].charAt(y) != '#' && map[x].charAt(y) != 'F';
    }
    
    static boolean check_Joe(Node node) {
        return fire[node.x][node.y] > node.step && map[node.x].charAt(node.y) != '#' && vis[node.x][node.y] != 1 && 
               map[node.x].charAt(node.y) != 'F';
    }
}
class Node {
    int x,y,step;
    Node() {}
    Node(int x,int y,int step) {
        this.x = x;
        this.y = y;
        this.step = step;
    }
}

K - 迷宫问题展开目录

基础的 bfs 问题，关键在于打印路径，考虑到保存路径，所以就没有直接用队列，而是用数组模拟的队列，这样能够将东西都保存起来而不弹出

import java.util.*;

public class Main {
    static int[][] map = new int[5][5];
    static int[][] vis = new int[5][5];
    static int[][] move = {{0,1},{0,-1},{1,0},{-1,0}};
    static Node[] q = new Node[20];
    
    static void bfs() {
        int head = 0;
        int tail = 0;
        q[tail] = new Node(0,0,-1);
        vis[0][0] = 1;
        tail++;
        while(head < tail) {
            boolean flag = false;//找没找到终点
            for(int i = 0;i < 4;i++) {
                int nx = q[head].x + move[i][0];
                int ny = q[head].y + move[i][1];
                if(check(nx,ny)) {
                    vis[nx][ny] = 1;
                    q[tail] = new Node(nx,ny,head);
                    tail++;
                }
                if(nx == 4 && ny == 4) {
                    flag = true;
                    break;
                }
            }
            if(flag) {
                print(q[tail - 1]);
                break;
            }
            head++;
        }
    }
    
    static void print(Node node) {
        if(node.pre == -1) {
            System.out.println("(" + node.x + ", " + node.y + ")");
            return;
        } else {
            print(q[node.pre]);
            System.out.println("(" + node.x + ", " + node.y + ")");
        }
    }
    
    static boolean check(int x,int y) {
        return x >= 0 && x < 5 && y >= 0 && y < 5 && vis[x][y] != 1 && map[x][y] != 1;
    }
    
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        for(int i = 0;i < 5;i++)
            for(int j = 0;j < 5;j++) 
                map[i][j] = cin.nextInt();
        for(int i = 0;i < 20;i++)
            q[i] = new Node();
        bfs();
    }
}
class Node {
    int x,y,pre;//来到此点的出发点
    Node() {}
    Node(int x,int y,int pre) {
        this.x = x;
        this.y = y;
        this.pre = pre;
    }
}

L-Oil Deposits展开目录

水题，遍历地图，找到 '@' 就进去 dfs 遍历，并且 ans++，然后将每次遍历到的 '@' 都标记为访问过

import java.util.*;

public class Main {
    static int n,m;
    static String[] map;//地图
    static int[][] vis;//标记是否访问过
    static int ans;//答案
    static int[][] move = {{0,1},{0,-1},{1,0},{-1,0},{-1,-1},{1,-1},{-1,1},{1,1}};
    
    static void dfs(int x,int y) {
        for(int i = 0;i < 8;i++) {
            int nx = x + move[i][0];
            int ny = y + move[i][1];
            if(check(nx,ny)) {
                vis[nx][ny] = 1;
                dfs(nx,ny);
            }
        }
    }
    static boolean check(int x,int y) {
        return x >= 0 && x < n && y >= 0 && y < m && map[x].charAt(y) == '@' && vis[x][y] == 0;
    }
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        while(cin.hasNext()) {
            n = cin.nextInt();
            m = cin.nextInt();
            map = new String[n];
            vis = new int[n][m];
            ans = 0;
            if(n == 0 && m == 0)
                break;
            for(int i = 0;i < n;i++) 
                map[i] = cin.next();
            for(int i = 0;i < n;i++) 
                for(int j = 0;j < m;j++) 
                    if(map[i].charAt(j) == '@' && vis[i][j] == 0) {
                        ans++;
                        vis[i][j] = 1;
                        dfs(i,j);
                    }
            System.out.println(ans);
        }
    }
}

M - 非常可乐展开目录

bfs 模拟即可，需要注意的是，只要三个容器里任意两个相等即可，不一定要杯子两个相等

#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int Max = 101;
//一共三个杯子，知道总和，所以只需要前两个杯子的状态，就可以进行判断了
int s,n,m;
int vis[Max][Max];
typedef struct node {
    int x,y,z;//x代表可乐罐，y,z代表两个杯子
    int step;
}Node;

//模拟的顺序是：x to y,x to z,y to x,y to z,z to x,z to y
int bfs() {
    memset(vis,0,sizeof(vis));
    Node now,next;
    queue<Node> q;
    now.x = s,now.y = 0,now.z = 0,now.step = 0;
    vis[now.x][now.y] = 1;
    q.push(now);
    while(q.size()) {
        now = q.front();
        q.pop();
        if((now.x == now.y && now.z == 0) || (now.x == now.z && now.y == 0) || (now.y == now.z && now.x == 0))
            return now.step;
        for(int i = 0;i < 6;i++) {
            switch(i) {
                case 0:
                    if(now.x != 0 && now.y != n)
                        next.x = now.x - (n - now.y),next.y = n,next.z = now.z;
                    break;
                case 1:
                    if(now.x != 0 && now.z != m)
                        next.x = now.x - (m - now.z),next.y = now.y,next.z = m;
                    break;
                case 2:
                    if(now.y != 0)
                        next.x = now.x + now.y,next.y = 0,next.z = now.z;
                    break;
                case 3:
                    if(now.y != 0 && now.z != m) {
                        if(now.y + now.z > m)
                            next.x = now.x,next.y = now.y - (m - now.z),next.z = m;
                        else
                            next.x = now.x,next.y = 0,next.z = now.z + now.y;
                    }
                    break;
                case 4: 
                    if(now.z != 0)
                        next.x = now.x + now.z,next.y = now.y,next.z = 0;
                    break;
                case 5: 
                        if(now.z != 0 && now.y != n) {
                            if(now.y + now.z > n)
                                next.x = now.x,next.y = n,next.z = now.z - (n - now.y);
                            else
                                next.x = now.x,next.y = now.y + now.z,next.z = 0;
                        }
                        break;
            }
            if(vis[next.x][next.y])
                continue;
            vis[next.x][next.y] = 1;
            next.step=now.step + 1;
            q.push(next);
        }
    }
    return -1;
}

int main() {
    while(~scanf("%d %d %d",&s,&n,&m)) {
        if(!s && !n && !m)
            break;
        memset(vis,0,sizeof(vis));
        int ans = bfs();
        if(ans == -1)
            printf("NO\n");
        else
            printf("%d\n",ans);
    }
    return 0;
}

N-Find a way展开目录

用一个三维数组去标记，注意求的是两个人在路上用的总时间

import java.util.*;
public class Main {
    static int n,m;
    static String[] map;
    static int[][][] vis;
    static int[][] move = {{0,1},{0,-1},{1,0},{-1,0}};
    static Queue<Node> q;
    
    static int bfs(Node a,Node b) {
        q.add(a);q.add(b);
        int res = Integer.MAX_VALUE;
        vis[a.x][a.y][a.op] = 1;vis[b.x][b.y][b.op] = 1;
        Node cur;
        while(!q.isEmpty()) {
            cur = new Node(q.peek().x,q.peek().y,q.poll().op);
            if(map[cur.x].charAt(cur.y) == '@' && vis[cur.x][cur.y][0] != 0 && vis[cur.x][cur.y][1] != 0)
                res = Math.min(res,vis[cur.x][cur.y][0] + vis[cur.x][cur.y][1]);
            for(int i = 0;i < 4;i++) {
                Node new_cur = new Node(cur.x + move[i][0],cur.y + move[i][1],cur.op);
                if(check(new_cur.x,new_cur.y,new_cur.op)) {
                    vis[new_cur.x][new_cur.y][new_cur.op] = vis[cur.x][cur.y][cur.op] + 1;
                    q.add(new_cur);
                }
            }
        }
        return res - 2;
    }
    
    static boolean check(int x,int y,int i) {
        return x >= 0 && x < n && y >= 0 && y < m  && map[x].charAt(y) != '#' && vis[x][y][i] == 0;
    }
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        while(cin.hasNext()) {
            q = new LinkedList<Node>();
            n = cin.nextInt();
            m = cin.nextInt();
            vis = new int[205][205][2];
            map = new String[205];
            Node a = new Node();
            Node b = new Node();
            for(int i = 0;i < n;i++) {
                map[i] = cin.next();
                for(int j = 0;j < m;j++) {
                    if(map[i].charAt(j) == 'Y') 
                        a = new Node(i,j,0);
                    if(map[i].charAt(j) == 'M') 
                        b = new Node(i,j,1);
                }
            }
            int ans = bfs(a,b);
            System.out.println(ans * 11);
        }
    }
}
class Node {
    int x,y,op;//op等于0代表y,op等于1代表m
    Node(){}
    Node(int x,int y,int op) {
        this.x = x;
        this.y = y;
        this.op = op;
    }
}