[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×10cur×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来保存状态，循环模拟，如果找到了和目标一样的排列，就返回答案；如果找到了已经存在于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;
}
}