MENU

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

August 26, 2018 • Read: 3643 • 算法阅读设置

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;
    }
}
Last Modified: May 12, 2021
Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment