kuangbin专题一简单搜索

tips:大家评论的时候写一下邮箱和昵称呀,头像是根据昵称和邮箱随机生成的😁

kuangbin专题合集

ACM正确入门方式——数学lover

——————————分割线——————————

2020-01-27更新
快要考研了,在acm里面也没什么成就,唉
下学期还要参加蓝桥杯,就趁寒假在家复(yu)习考研课程的间隙练一练题吧,蓝桥杯报的Java组,水一个国奖算了,大学四年最后两个愿望了,蓝桥杯拿个国奖+考研顺利,加油!!!

2020-0202更新

终于把暑假挖的坑给填上了,接下来要开始专题四,这几天都没有背单词看高数,得多看一看了。

——————————分割线——————————

题目列表

  1. POJ 1321 棋盘问题 AC: 2018-07-17 23:54:31
  2. POJ 2251 Dungeon Master AC: 2019-09-19 18:32:04
  3. POJ 3278 Catch That Cow AC: 2019-09-21 19:37:10
  4. POJ 3279 Fliptile AC: 2019-09-22 16:09:25
  5. POJ 1426 Find The Multiple AC: 2019-09-23 20:09:26
  6. POJ 3126 Prime Path AC: 2019-09-24 22:48:09
  7. POJ 3087 Shuffle’m Up AC: 2020-01-31 18:33:39
  8. POJ 3414 Pots AC: 2020-02-01 18:51:43
  9. FZU 2150 Fire Game 待定,oj挂了
  10. UVA 11624 Fire! AC: 2020-02-02 16:13:29
  11. POJ 3984 迷宫问题 AC: 2020-01-27 22:42:36
  12. HDU 1241 Oil Deposits AC: 2020-02-02 17:05:05
  13. HDU 1495 非常可乐 AC: 2020-01-31 16:58:53
  14. HDU 2612 Find a way AC: 2020-02-02 17:58:08

POJ-1321 棋盘问题

题意

就是在棋盘上放棋子,放的时候不能同行同列,和八皇后问题类似,只不过空白的地方不能放。这是我去年暑假acm训练时写的,现在已经忘了当时咋写的了,看着自己WA了好多发,太菜了。。。dfs时记得复原。

题解

dfs吧,没什么可说的,八皇后模板题。好烦啊,POJ不能用万能头文件。。。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
//#include <bits/stdc++.h>
#include <string.h>

typedef long long ll;
const int INF = 1 << 30;
const int maxn = 1e5;
using namespace std;

int n, m, ans;
char pan[10][10];
bool vis[10];
int cnt;

void dfs(int l)
{
if(cnt == m)
{
ans++;
return;
}
else if(l>=n)
return;
else
{
for(int i=0; i<n; i++)
if(pan[l][i]=='#' && !vis[i])
{
cnt++;
vis[i]=1;
dfs(l+1);
vis[i]=0;
cnt--;
}
dfs(l+1);
}

return;
}

int main()
{
//ios::sync_with_stdio(0), cin.tie(0);

while(cin >>n >>m)
{
if(n==-1 && m==-1)
break;
memset(vis, 0, sizeof(vis));
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
cin >>pan[i][j];

ans = cnt = 0;
dfs(0);
cout <<ans <<endl;
}

return 0;
}

POJ-2251 Dungeon Master

题意

一个3D迷宫,总共六个方向,上下左右前后。有的地方不能走有的能走,给出起点终点,问你能不能走到终点,如果能的话应该是求用时最短的吧(题目中没说,一开始用dfsWA了,后来看别人都用bfs才发现是不是要求最短路)。没移动一次要花费一分钟。

题解

bfs,一开始用bfs一直内存超限,快给我郁闷死了。。。要把走过的点用#堵上,防止多余的结点入队列。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>
#include <stdio.h>
#include <queue>
#include <string.h>

using namespace std;
const int maxn = 31;

struct node
{
int x, y, z, step;
};

node make_node(int x, int y, int z, int step)
{
node a;
a.x = x, a.y = y, a.z = z, a.step=step;
return a;
}

int main()
{

int l, r, c;
char mp[maxn][maxn][maxn];
int dx[6]= {1, -1, 0, 0, 0, 0};
int dy[6]= {0, 0, 1, -1, 0, 0};
int dz[6]= {0, 0, 0, 0, 1, -1};

while (cin >>l >>r >>c && l+r+c)
{
int x, y, z;
queue<node> q;
for(int i=0; i<l; i++)
{
for(int j=0; j<r; j++)
for(int k=0; k<c; k++)
{
cin >>mp[i][j][k];
if(mp[i][j][k]=='S')
q.push(make_node(i, j, k, 0));
if(mp[i][j][k]=='E')
{
x = i;
y = j;
z = k;
}
}
getchar();
}

bool flag = false;
while(!q.empty())
{
node a = q.front();
q.pop();

if(a.x==x && a.y==y && a.z==z)
{
flag = true;
cout <<"Escaped in "<<a.step <<" minute(s)." <<endl;
break;
}

for (int i = 0; i < 6; ++i)
{
if(mp[a.x+dx[i]][a.y+dy[i]][a.z+dz[i]]!='#')
if(a.x+dx[i]>=0 && a.x+dx[i]<l && a.y+dy[i]>=0 && a.y+dy[i]<r && a.z+dz[i]>=0 && a.z+dz[i]<c)
{
q.push(make_node(a.x+dx[i], a.y+dy[i], a.z+dz[i], a.step+1));
mp[a.x+dx[i]][a.y+dy[i]][a.z+dz[i]] = '#';
}
}
}

if(flag)
continue;
else
cout <<"Trapped!" <<endl;
}

return 0;
}

POJ-3287 Catch That Cow

题意

你的牛跑了,要把它抓回来。你的位置在n,牛的位置在k,牛不会跑,你要用最少的时间走到牛的位置。你们的位置都在同一个数轴上,只有左右两个方向,你有三种走法,左走一步、右走一步或者传送到你当前坐标的二倍的位置,这三种走法都只花费一分钟。n和k都小于等于100000

题解

只有三种操作,求最短时间,可以用bfs。bfs要设置一个vis数组,注意不能数组越界。还要注意当n==k的时候。一开始一直超内存,后来发现要设一个vis数组剪枝。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <queue>
#include <string.h>

using namespace std;
const int maxn = 1e5+10;
bool vis[maxn];
struct node
{
int p, t;
};

node make_node(int p, int t)
{
node a;
a.p = p;
a.t = t;

return a;
}

int main()
{
int n, k;
while(cin >>n >>k)
{
if(n==k)
{
cout <<0 <<endl;
continue;
}

memset(vis, 0, sizeof vis);
queue<node> q;
q.push(make_node(n, 0));
vis[n] = true;

while(!q.empty())
{
node a = q.front();
q.pop();

if(a.p+1==k || a.p-1==k || a.p*2==k)
{
cout <<a.t+1 <<endl;
break;
}

if(a.p<k)
{
if(a.p+1<=100000 && !vis[a.p+1])
{
q.push(make_node(a.p+1, a.t+1));
vis[a.p+1] = true;
}
if(a.p*2-k<k-a.p && a.p*2<=100000 && !vis[a.p*2])
{
q.push(make_node(a.p*2, a.t+1));
vis[a.p*2] = true;
}
if(a.p-1>=0 && !vis[a.p-1])
{
q.push(make_node(a.p-1, a.t+1));
vis[a.p-1] = true;
}
}
else if(a.p>k && a.p-1>=0 && !vis[a.p-1])
{
q.push(make_node(a.p-1, a.t+1));
vis[a.p-1] = true;
}
}
}
return 0;
}

POJ-3279 Fliptile

题意

有n*m个方格,每个方格都有一块瓷砖,瓷砖的两面分别是黑色和白色,当你翻转瓷砖时瓷砖会从白色翻转成黑色,或者从黑色翻转成白色。样例输入为每个方格瓷砖的初始颜色,0代表白色,1代表黑色。现在让你的奶牛来将所有格子翻成白色,由于奶牛的蹄子比较大,它每次反转的时会将相邻的瓷砖也翻转过来,即上下左右的瓷砖。最后输出每个瓷砖的翻转次数,要求总的翻转次数最少,如果答案有多种,则输出字典序最小的那个答案。

题解

这题有个最重要的思想,就是第i层如果有黑色瓷砖,要通过第i+1层的翻转将其翻转成白色。这样只用保证前一层没有黑色即可,不用管当前层翻转成什么样,也不用管下一层。这样的话只要第一层的状态确定,后面所有的状态都确定了。因为第二层需要将第一层的黑瓷砖翻成白色的,这个过程中第二层可能会出现黑瓷砖,再用第三层将第二层翻转成白色的,再用第四层将。。。我们可以枚举第一层所有的状态,即每一块瓷砖翻或不翻,总共有2^m个,然后用第二层将第一层翻成白色。。。用最后一层将倒数第二层翻成白色,因为后面没有瓷砖来翻转最后一层了,所有我们通过判断最后一层有没有黑色瓷砖,就可以判断这个方法是否可行。

输出次数最少的那一个可以每次翻转记录一下,最后对比所有可能性的翻转次数取最小即可。

字典序最小,即输出答案时每行的字典序最小,每行的字典序即把所有数字串成一个字符串,让他们字典序最小,即将0 0 0 1 1串成00011,而00011的字典序比10010小。保证字典序最小可以先保证第一行字典序最小,第一行有2^m种可能,我们把没个瓷砖看成二进制的一位数,那第一行的所有操作就是0~(1<<m-1),我们枚举的时候直接从0开始枚举就行了。

一开始写的时候怎么想都没思路,最后看了别人的题解才写出来,还是做题太少了,太菜了。。。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
#include <cstring>

using namespace std;
const int maxn = 30;
const int INF = 1 << 30;

int n, m, turnnum, turnans;
int mp[maxn][maxn], a[maxn][maxn], fn[maxn][maxn], ans[maxn][maxn];
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };

void turn(int i, int j)
{
fn[i][j] = 1;
turnnum++;
a[i][j] = !a[i][j];
for (int k = 0; k < 4; k++)
a[i + dx[k]][j + dy[k]] = !a[i + dx[k]][j + dy[k]];
}

int main()
{
while (cin >>n >>m)
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> mp[i][j];
}
}

int lp = 1 << m;
turnans = INF;
for (int i = 0; i < lp; i++)
{
memset(fn, 0, sizeof fn);
memcpy(a, mp, sizeof mp);
turnnum = 0;
int p = i;
for (int j = 1; j <= m; j++)
{
if (p & 1)
turn(1, j);
p >>= 1;
}

for (int j = 2; j <= n; j++)
{
for (int k = 1; k <= m; k++)
{
if (a[j - 1][k])
turn(j, k);
}
}


int j;
for (j = 1; j <= m; j++)
{
if (a[n][j])
break;
}
if (j == m+1 && turnnum < turnans)
{
turnans = turnnum;
memcpy(ans, fn, sizeof fn);
}
}

if (turnans == INF)
cout << "IMPOSSIBLE" << endl;
else
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cout << ans[i][j] << ' ';
}cout << endl;
}
}
}

return 0;
}

参考

POJ3279 二进制的搜索

POJ-1426 Find The Multiple

题意

给你一个不超过200的数n,让你求一个数m,m不超过100位,m只包含0和1且(m%n)== 0。

题解

不知道为什么,直接定义longlong + BFS就过了。。。一开始想模拟,还超时了,菜。。。

在网上看到有个大佬在用这题讲同余模定理,抽空看一下。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <queue>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#define ll long long

using namespace std;
const int maxn = 1e5+10;
queue<int> q;

int main()
{
unsigned ll n, m=1;

while(cin >>n && n)
{
while(!q.empty())q.pop();
m = 1;
q.push(m);
if(m%n==0)
{
cout <<m <<endl;
continue;
}
while(!q.empty())
{
m = q.front();
q.pop();
m *= 10;
if(m%n==0)
{
cout <<m <<endl;
break;
}
q.push(m);
m += 1;
if(m%n==0)
{
cout <<m <<endl;
break;
}
q.push(m);
}
}
return 0;
}

POJ-3126 Prime Path

题意

测试数据不超过一百组,每组给出两个四位素数,要求你将第一个数字变换成第二个数字。没回只能变换一位数字,而且首位数字不能变成0,变换过的数字也必须为素数。每次变换需要花1磅,问你从第一个数字变换到第二个数字最小花费是多少。

题解

最少花费,肯定BFS了,先用线性素数筛打个表,每次进队的数据查表时间复杂度为O(1),然后每一层循环,要把四位数字全换一遍,换一个数字进一次队列,用vis数组剪枝。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <iostream>
#include <queue>
#include <string.h>
#include <stdlib.h>
#include <algorithm>

#define ll long long

using namespace std;
const int maxn = 1e5+10;
int prime[maxn], pNum = 0;
bool p[maxn] = {false}, vis[maxn]={false};

struct num
{
int a, cos;
};

num make_num(int a, int cos)
{
num x;
x.a = a;
x.cos = cos;
return x;
}

void eulerSieve(int n)
{
for (int i = 2; i <= n; i++)
{
if (p[i] == false)
prime[pNum++] = i;
for (int j = 0; j < pNum; j++)
{
if (i * prime[j] > n)
break;
p[i * prime[j]] = true;
if (i % prime[j] == 0)
break;
}
}
}

int main()
{
eulerSieve(100000);
int t;
cin >>t;
while(t--)
{
memset(vis, false, sizeof vis);
int a, b;
cin >>a >>b;

queue<num> q;
q.push(make_num(a, 0));
vis[a] = true;

while(!q.empty())
{
num x = q.front();
q.pop();
if(x.a==b)
{
cout <<x.cos <<endl;
break;
}

for(int i=1; i<10; i++)
{
int y = x.a;
if(y/1000==i) continue;
y = i*1000+y%1000;
if(!vis[y] && !p[y])
{
q.push(make_num(y, x.cos+1));
vis[y] = true;
}
}

for(int i=0; i<10; i++)
{
int y = x.a;
if(y/100%10==i) continue;
y = (y/1000*10+i)*100+y%100;
if(!vis[y] && !p[y])
{
q.push(make_num(y, x.cos+1));
vis[y] = true;
}
}

for(int i=0; i<10; i++)
{
int y = x.a;
if(y%100/10==i) continue;
y = (y/100*10+i)*10+y%10;
if(!vis[y] && !p[y])
{
q.push(make_num(y, x.cos+1));
vis[y] = true;
}
}

for(int i=0; i<10; i++)
{
int y = x.a;
if(y%10==i) continue;
y = y/10*10+i;
if(!vis[y] && !p[y])
{
q.push(make_num(y, x.cos+1));
vis[y] = true;
}
}
}
}

return 0;
}

POJ-3087 Shuffle’m Up

题意

根本不是搜索题,就是简单的模拟题。。。
给你两组牌s1,s2,每组牌的数量相同,分为两个步骤洗牌和分牌。
洗牌:分别从s1和s2底部每次抽一张牌放到桌上,先从s2的底部开始抽,组成一组牌s12(类似于入栈操作)。
分牌:将组成的s12再分成s1和s2,将s12下半部分组成s1,将s12的上半部分组成s2。
牌的颜色总共有A~H种,现在又给一组牌s3,问经过几次洗牌能将牌洗成s3的样子,如果可以则输出数据组序号和洗牌次数,不能则输出数据组序号和-1 。(序号从1开始)

题解

一开始看到题要求最少的洗牌次数,以为要用bfs,然后在想怎么用bfs的时候发现他每一步的操作都只有固定的一种,没什么可搜索的啊,才发现就是个暴力模拟题。
就是用队列模拟洗牌和发牌的过程,如果不能洗成目标牌组的话会发现洗着洗着s1和s2又回到原来的样子了,这个手算一下样例的第二组数据就知道了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
import java.util.*;

public class Main {

public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n = cin.nextInt();

for (int i = 0; i < n; i++) {
int x = cin.nextInt();
String s1 = cin.nextLine();
s1 = cin.nextLine();
String s2 = cin.nextLine();
String s3 = cin.nextLine();
Queue<Character> queue = new LinkedList<Character>();
String s4 = s1, s5 = s2;

boolean flag = false;
int step = 0;
while (true) {
step++;

for (int j = 0; j < s1.length(); j++) {
queue.offer(s5.charAt(j));
queue.offer(s4.charAt(j));
}

String ss = "";
for (int j = 0; j < 2 * x; j++) {
ss += queue.peek();
queue.offer(queue.peek());
queue.poll();
}
if (ss.equals(s3)) {
flag = true;
break;
}

s4 = "";
s5 = "";
for (int j = 0; j < x; j++) {
s4+=queue.peek();
queue.poll();
}
for (int j = 0; j < x; j++) {
s5+=queue.peek();
queue.poll();
}
if (s4.equals(s1) && s5.equals(s2)){
break;
}
}
if (flag){
System.out.println(i+1 + " " + step);
}else {
System.out.println(i+1 + " " + -1);
}
}
}
}

POJ-3414 Pots

题意

这题和HDU1495非常可乐太像了,不过比那个复杂一些,操作方法变了一下,而且需要回溯记录路径。感觉是可乐问题+迷宫问题。。。
一开始有两个空罐子A和B,每个罐子都有固定容量(倒水题惯例),问你经过一系列操作是否可以使得任意一个罐子中的水有C升,如果可以则求最少操作次数和所有操作步骤,如果不可以则输出”impossible”。操作有如下几种:

  1. 将A或B灌满水
  2. 将A或B的水全部倒掉
  3. 将A的水倒给B,或将B的水倒给A

题解

求最少操作次数和操作步骤,用bfs+回溯,vis去重。(用java写这种题代码好长啊,而且感觉我写的代码好笨重)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
import java.util.*;

class Pot {//用于记录每个状态
int a, b;
int step;

public Pot(int a, int b, int step) {
this.a = a;
this.b = b;
this.step = step;
}

public Pot(Pot x) {
this.a = x.a;
this.b = x.b;
this.step = x.step;
}
}

class View {//vis数组
boolean v;
int op;//操作种类
int prex, prey;//前驱结点
}

public class Main {

static String[] opt = new String[]{//所有操作种类,方便输出
"FILL(1)", "FILL(2)", "DROP(1)", "DROP(2)", "POUR(1,2)", "POUR(2,1)"
};
static View[][] vis = new View[105][105];

public static void print(int x, int y) {
if (vis[x][y].prex != -1 && vis[x][y].prey != -1)
print(vis[x][y].prex, vis[x][y].prey);
if (vis[x][y].op != -1)
System.out.println(opt[vis[x][y].op]);
return;
}

public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int A = cin.nextInt();
int B = cin.nextInt();
int C = cin.nextInt();


for (int i = 0; i < 105; i++) {
for (int j = 0; j < 105; j++) {
vis [i][j] = new View();
vis[i][j].v = false;
}
}
vis[0][0].v = true;
vis[0][0].op = -1;
vis[0][0].prex = -1;
vis[0][0].prey = -1;
Queue<Pot> queue = new LinkedList<Pot>();
Pot now = new Pot(0, 0, 0);
queue.offer(now);

boolean flag = false;
while (!queue.isEmpty()) {
now = queue.peek();
queue.poll();
if (now.a == C || now.b == C) {
flag = true;
break;
}

for (int i = 0; i < 6; i++) {
Pot next = new Pot(now);
if (i == 0 && next.a != A && !vis[A][next.b].v) {
vis[A][next.b].v = true;
vis[A][next.b].op = 0;
vis[A][next.b].prex = now.a;
vis[A][next.b].prey = now.b;
next.a = A;
next.step++;
queue.offer(next);
continue;
}
if (i == 1 && next.b != B && !vis[next.a][B].v) {
vis[next.a][B].v = true;
vis[next.a][B].op = 1;
vis[next.a][B].prex = now.a;
vis[next.a][B].prey = now.b;
next.b = B;
next.step++;
queue.offer(next);
continue;
}
if (i == 2 && next.a != 0 && !vis[0][next.b].v) {
vis[0][next.b].v = true;
vis[0][next.b].op = 2;
vis[0][next.b].prex = now.a;
vis[0][next.b].prey = now.b;
next.a = 0;
next.step++;
queue.offer(next);
continue;
}
if (i == 3 && next.b != 0 && !vis[next.a][0].v) {
vis[next.a][0].v = true;
vis[next.a][0].op = 3;
vis[next.a][0].prex = now.a;
vis[next.a][0].prey = now.b;
next.b = 0;
next.step++;
queue.offer(next);
continue;
}
if (i == 4 && next.a != 0 && next.b != B) {
int vo = B - next.b;
if (next.a > vo) {
next.a -= vo;
next.b = B;
} else {
next.b += next.a;
next.a = 0;
}
if (!vis[next.a][next.b].v) {
vis[next.a][next.b].v = true;
vis[next.a][next.b].op = 4;
vis[next.a][next.b].prex = now.a;
vis[next.a][next.b].prey = now.b;
next.step++;
queue.offer(next);
}
continue;
}
if (i == 5 && next.a != A && next.b != 0) {
int vo = A - next.a;
if (next.b > vo) {
next.b -= vo;
next.a = A;
} else {
next.a += next.b;
next.b = 0;
}
if (!vis[next.a][next.b].v) {
vis[next.a][next.b].v = true;
vis[next.a][next.b].op = 5;
vis[next.a][next.b].prex = now.a;
vis[next.a][next.b].prey = now.b;
next.step++;
queue.offer(next);
}
continue;
}
}
}

if (flag){
System.out.println(now.step);
print(now.a, now.b);
}else {
System.out.println("impossible");
}
}
}

FZU-2150 Fire Game

题意

一个n×m的地图,有的地方是草,有的地方是空的,选两个点同时点火,问是否能将地图上的草烧完,如果是则求出最短燃烧时间。火烧到相邻带有草的格子所需要的时间为1,相邻表示上下左右的格子(即过一个时间,其上有左右有草的格子同时着火),选择的两个点可以相同

题解

双起点bfs,我的方法比较笨,先用bfs求出图中草有几个不相邻的分区,如果分区数大于2肯定不能完成,因为最多只能选择两个起点烧,如果两个一下,则将每个分区中的所有点分别加入一个队列,依次从该分区的每个点进行一次bfs遍历该分区,求出其中用时最短的。(由于oj挂了,我也没有测试,只过了样例,但是觉得这题应该没什么坑,而且数据也挺小的,总共才1e6,所以先写着,以后等可以交了我再改一下)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
import java.util.*;

class Point {
char ch;
int index, x, y, step;

public Point(int x, int y) {
this.x = x;
this.y = y;
}

public Point() {
}
}

public class Main {

static int[] dx = {1, -1, 0, 0};
static int[] dy = {0, 0, 1, -1};

static void reset(Point[][] mp){
for (int i = 0; i < 15; i++) {
for (int j = 0; j < 15; j++) {
mp[i][j].step = 0;
}
}
}

public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int t = cin.nextInt();
Point[][] mp = new Point[15][15];
for (int i = 0; i < 15; i++) {
for (int j = 0; j < 15; j++) {
mp[i][j] = new Point();
mp[i][j].x = i;
mp[i][j].y = j;
}
}

for (int i = 0; i < t; i++) {
int n = cin.nextInt(), m = cin.nextInt();
String s = cin.nextLine();
for (int j = 0; j < n; j++) {
s = cin.nextLine();
for (int k = 0; k < s.length(); k++) {
mp[j][k].ch = s.charAt(k);
mp[j][k].index = -1;
mp[j][k].step = 0;
}
}

Queue<Point> queue = new LinkedList<Point>();
Queue<Point> q1 = new LinkedList<Point>();
Queue<Point> q2 = new LinkedList<Point>();
int num = 0;
for (int j = 0; j < n; j++) {
for (int k = 0; k < m; k++) {
if (mp[j][k].ch == '#' && mp[j][k].index == -1) {
Point now = mp[j][k];
now.index = num;
if (num==0)q1.offer(now);
else q2.offer(now);
queue.offer(now);
while (!queue.isEmpty()) {
now = queue.peek();
queue.poll();

for (int l = 0; l < 4; l++) {
if (now.x + dx[l] >= 0 && now.x + dx[l] < n && now.y + dy[l] >= 0 && now.y + dy[l] < m && mp[now.x + dx[l]][now.y + dy[l]].ch == '#' && mp[now.x + dx[l]][now.y + dy[l]].index==-1) {
mp[now.x + dx[l]][now.y + dy[l]].index = num;
queue.offer(mp[now.x + dx[l]][now.y + dy[l]]);
if (num==0)q1.offer(mp[now.x + dx[l]][now.y + dy[l]]);
else q2.offer(mp[now.x + dx[l]][now.y + dy[l]]);
}
}
}
num++;
}
}
}
if (num>2){
System.out.println("Case " + (i+1) + ": " + -1);
continue;
}
int t1=10000, t2=10000;
while (!q1.isEmpty()){
char[][] mmp = new char[15][15];
for (int j = 0; j < 15; j++) {
for (int k = 0; k < 15; k++) {
mmp[j][k] = mp[j][k].ch;
mp[j][k].step = 0;
}
}

while (!queue.isEmpty()) queue.poll();
Point now = q1.peek();
q1.poll();
queue.offer(now);
mmp[now.x][now.y] = '.';

while (!queue.isEmpty()){
now = queue.peek();
queue.poll();

for (int j = 0; j < 4; j++) {
if (now.x + dx[j] >= 0 && now.x + dx[j] < n && now.y + dy[j] >= 0 && now.y + dy[j] < m && mmp[now.x + dx[j]][now.y + dy[j]] == '#'){
mmp[now.x + dx[j]][now.y + dy[j]] = '.';
mp[now.x + dx[j]][now.y + dy[j]].step = now.step+1;
queue.offer(mp[now.x + dx[j]][now.y + dy[j]]);
}
}
}
t1 = Math.min(t1, now.step);
}
if (num==2){
while (!q2.isEmpty()){
char[][] mmp = new char[15][15];
for (int j = 0; j < 15; j++) {
for (int k = 0; k < 15; k++) {
mmp[j][k] = mp[j][k].ch;
mp[j][k].step = 0;
}
}

while (!queue.isEmpty()) queue.poll();
Point now = q2.peek();
q2.poll();
queue.offer(now);
mmp[now.x][now.y] = '.';

while (!queue.isEmpty()){
now = queue.peek();
queue.poll();

for (int j = 0; j < 4; j++) {
if (now.x + dx[j] >= 0 && now.x + dx[j] < n && now.y + dy[j] >= 0 && now.y + dy[j] < m && mmp[now.x + dx[j]][now.y + dy[j]] == '#'){
mmp[now.x + dx[j]][now.y + dy[j]] = '.';
mp[now.x + dx[j]][now.y + dy[j]].step = now.step+1;
queue.offer(mp[now.x + dx[j]][now.y + dy[j]]);
}
}
}
t2 = Math.min(t2, now.step);
}
}

if (t1==10000 || t2==10000)
System.out.println("Case " + (i+1) + ": " + Math.min(t1, t2));
else
System.out.println("Case " + (i+1) + ": " + Math.max(t1, t2));
}
}
}

UVA-11624 Fire!

题意

火烧屁股,赶紧窜。。。
逃出迷宫,只要是挨着迷宫边缘的点都可以逃出迷宫。

题解

注意,本题起始时间可能有多个起始火苗!!!(一开始我也没注意到,偶然间在vj的评论里看到的不然我可能也被坑死了)其实就是个bfs的题,数据量比较大,容易超时,要注意一点。应该让火苗先走人再走,我是让每个人走过的点和被火苗烧过的点都变成墙,这样后来走的时候就不会再走了。
我把火苗和人放在了两个队列里面了,一开始想复杂了,每个点都有一个属性step,用来记录当前时间,如果进入下一个时间点就让该时间点的火苗全部走一遍,然后再让人走。
后来看到别人让火苗和人放在一个队列里面了,只有一开始处理一下,先让所有起始的火苗先进队列,再让人的起始点进入队列就可以了。(不过我后来把我的代码改成这样超时了,就懒得再改了,一开始调试时用的输出代码忘记删了,他还给我判超时,我懵逼了好一会儿。。。)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
import java.util.*;

class Point {
int x, y, step;

public Point(int x, int y) {
this.x = x;
this.y = y;
}

public Point() {
}

public void setPoint(int x, int y, int step) {
this.x = x;
this.y = y;
this.step = step;
}

public Point(int x, int y, int step) {
this.x = x;
this.y = y;
this.step = step;
}

public Point(Point point) {
this.x = point.x;
this.y = point.y;
this.step = point.step;
}
}

public class Main {

static int[] dx = {1, -1, 0, 0};
static int[] dy = {0, 0, 1, -1};

static char[][] mp = new char[1005][1005];

public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int t = cin.nextInt();
while (t-- > 0) {
int r = cin.nextInt(), c = cin.nextInt();
String s = cin.nextLine();
Queue<Point> Fire = new LinkedList<Point>();
Queue<Point> queue = new LinkedList<Point>();
Point now = new Point();
for (int i = 0; i < r; i++) {
s = cin.nextLine();
for (int j = 0; j < s.length(); j++) {
mp[i][j] = s.charAt(j);
if (mp[i][j] == 'F') {
mp[i][j] = '#';
Fire.offer(new Point(i, j, 0));
}
if (mp[i][j] == 'J') {
mp[i][j] = '#';
now.setPoint(i, j, 0);
queue.offer(now);
}
}
}

int CurStep = -1;
boolean flag = false;
while (!queue.isEmpty()) {
now = queue.peek();
queue.poll();
if (now.y == 0 || now.y == c - 1 || now.x == 0 || now.x == r - 1) {
flag = true;
break;
}

if (now.step > CurStep) {//先烧火
CurStep++;

Point CurFire;
while (!Fire.isEmpty()) {
CurFire = Fire.peek();
if (CurFire.step != CurStep)
break;
Fire.poll();

for (int i = 0; i < 4; i++) {
Point next = new Point(CurFire);
next.step++;
next.x += dx[i];
next.y += dy[i];
if (next.x >= 0 && next.x < r && next.y >= 0 && next.y < c && mp[next.x][next.y] != '#') {
mp[next.x][next.y] = '#';
Fire.offer(next);
}
}
}
}

for (int i = 0; i < 4; i++) {
Point next = new Point(now);
next.step++;
next.x += dx[i];
next.y += dy[i];
if (next.x >= 0 && next.x < r && next.y >= 0 && next.y < c && mp[next.x][next.y] != '#') {
mp[next.x][next.y] = '#';
queue.offer(next);
}
}
}

if (flag) System.out.println(now.step+1);
else System.out.println("IMPOSSIBLE");
}
}
}

POJ-3984 迷宫问题

太久没写题了,先拿个简单的练练手吧

Java在OJ交题有好多坑啊,这有一篇比较不错的博客讲的挺全的:JAVA在OJ上提交程序的注意事项
(一定要带上包名,别问我为什么知道的(手动狗头)。用Java写题总感觉怪怪的)

题意

给一个5×5的迷宫,1是墙,0是路,求出从左上角到右下角的最短路径并输出路径上每个结点的坐标,只能横着走或竖着走,不能斜着走。

题解

用bfs求最短路嘛,再定义一个Point结构体,记录前驱结点,最后用递归输出路径。注意逗号后面有一个空格。

其实他这个题的测试数据只有一个,就是样例。。。我看vj上面有人说直接把样例输出就过了。。。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
import java.util.*;

class Point{
int x, y;
int prex, prey;
int dis;

public Point(int x, int y){
this.x = x;
this.y = y;
}

public Point(){}
}

public class Main {

public static int[] dx = {1, -1, 0, 0};
public static int[] dy = {0, 0, 1, -1};
public static Point[][] p = new Point[5][5];

public static void print_point(int x, int y){
if(x==0 && y==0){
System.out.println("(" + x + ", " + y + ")");
return;
}
print_point(p[x][y].prex, p[x][y].prey);
System.out.println("(" + x + ", " + y + ")");
}

public static void main(String [] args){
int[][] mp = new int[5][5];
Scanner cin = new Scanner(System.in);
Queue<Point> q = new LinkedList<Point>();

for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
p[i][j] = new Point();
}
}

for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
mp[i][j] = cin.nextInt();
}
}

Point point = new Point(0, 0);
point.dis = 0;
point.prex = 0;
point.prey = 0;
q.offer(point);
while (!q.isEmpty()){
Point pp = q.peek();

if (pp.x==4 && pp.y==4)
break;

for (int i = 0; i < 4; i++) {
int xx = pp.x + dx[i];
int yy = pp.y + dy[i];

if(xx>=0 && xx<5 && yy>=0 && yy<5 && mp[xx][yy]!=1){
mp[xx][yy] = 1;
p[xx][yy].x = xx;
p[xx][yy].y = yy;
p[xx][yy].prex = pp.x;
p[xx][yy].prey = pp.y;
p[xx][yy].dis = pp.dis+1;
q.offer(p[xx][yy]);
}
}
q.poll();
}

print_point(4, 4);
}
}

HDU-1241 Oil Deposits

题意

求分块儿数目

题解

注意第二个样例,相邻的意思是相邻的八个格不是四个格
好像用dfs和bfs都可以,习惯了用bfs我就写了bfs。
每找到一个油田,就用bfs遍历这个油田,将油田的所有‘@’变为‘*’就可以了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
import java.util.*;

class Point {
int x, y;

public Point(int x, int y) {
this.x = x;
this.y = y;
}

public Point(Point point) {
this.x = point.x;
this.y = point.y;
}
}

public class Main {

static int[] dx = {1, -1, 0, 0, 1, 1, -1, -1};
static int[] dy = {0, 0, 1, -1, 1, -1, 1, -1};

static char[][] mp = new char[105][105];

public static void main(String[] args) {
Scanner cin = new Scanner(System.in);

while (true) {
int n = cin.nextInt(), m = cin.nextInt();
if (n==0 || m==0) break;

int ans = 0;
String s = cin.nextLine();
Queue<Point> queue = new LinkedList<Point>();
for (int i = 0; i < n; i++) {
s = cin.nextLine();
for (int j = 0; j < s.length(); j++) {
mp[i][j] = s.charAt(j);
}
}

for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (mp[i][j] == '@'){
ans++;
Point now = new Point(i, j);
queue.offer(now);
while (!queue.isEmpty()) {
now = queue.peek();
queue.poll();

for (int k = 0; k < 8; k++) {
Point next = new Point(now);
next.x += dx[k];
next.y += dy[k];
if (next.x >= 0 && next.x < n && next.y >= 0 && next.y < m && mp[next.x][next.y] == '@') {
mp[next.x][next.y] = '*';
queue.offer(next);
}
}
}
}
}
}

System.out.println(ans);
}
}
}

HDU-1495 非常可乐

题意

有三个杯子,s,n,m,每个被子都有自己的最大容量,初始时s装着满杯可乐。问最少经过几次倒水的步骤,能让其中两个杯子的可乐相等。由于每个杯子都没有刻度,所以每次倒水只能将一个杯子的可乐全部倒进另一个杯子,或者将另一个杯子倒满。(我一开始没理解这个,连样例都没看懂,一直在想他到底怎么倒水的)

题解

这题有两种解法,一种比较好想的bfs,另一种是数论(我不会。。。)给出网上dalao链接:HDU 1495 非常可乐(数论)

bfs解法:
当s中的初始为奇数时肯定不可平分。用一个类记录每个倒水的状态,包括当前每个杯子多少水和经过了多少步骤,每次倒水只有六种倒法:s->n,s->m,n->s,m->s,n->m,m->n,每次遍历这六种方法就行了。然后判断倒水的终止状态:任意两个杯子量相等且另一个杯子为空时才满足条件。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
import java.util.*;

class cola {
int[] cup = new int[3];
int step;
}

public class Main {

public static boolean[][][] vis = new boolean[105][105][105];

public static void main(String[] args) {
int s, n, m;
Scanner cin = new Scanner(System.in);
while (true) {
s = cin.nextInt();
n = cin.nextInt();
m = cin.nextInt();
if (s == 0 && n == 0 && m == 0) {
break;
}
if (s % 2 == 1) {
System.out.println("NO");
continue;
}

for (int i = 0; i < 105; i++) {
for (int j = 0; j < 105; j++) {
for (int k = 0; k < 105; k++) {
vis[i][j][k] = false;
}
}
}

vis[s][0][0] = true;
cola now = new cola();
now.cup[0] = s;
now.cup[1] = 0;
now.cup[2] = 0;
now.step = 0;
Queue<cola> queue = new LinkedList<cola>();
queue.offer(now);

boolean flag = false;
while (!queue.isEmpty()) {
now = queue.peek();
queue.poll();

if ((now.cup[0]==now.cup[1] && now.cup[2]==0) || (now.cup[0]==now.cup[2] && now.cup[1]==0) || (now.cup[1]==now.cup[2] && now.cup[0]==0)){
System.out.println(now.step);
flag = true;
break;
}

for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (i != j) {
cola next = new cola();
next.step = now.step;
System.arraycopy(now.cup, 0, next.cup, 0, 3);

int co = 0;
if (j == 0) co = s - next.cup[j];
if (j == 1) co = n - next.cup[j];
if (j == 2) co = m - next.cup[j];

if (next.cup[i] > co) {
next.cup[i] -= co;
next.cup[j] += co;
} else {
next.cup[j] += next.cup[i];
next.cup[i] = 0;
}
next.step += 1;

if (!vis[next.cup[0]][next.cup[1]][next.cup[2]]) {
vis[next.cup[0]][next.cup[1]][next.cup[2]] = true;
queue.offer(next);
}
}
}
}
}

if (!flag){
System.out.println("NO");
}
}
}
}

HDU-2612 Find a way

题意

地图上有好几个kfc(话说我也好久没吃kfc,好想吃kfc的薯条啊,不蘸番茄酱的。疫情太严重了,还是在家敲代码复习考研课吧。。。没事还能打一打无限火力,太快乐了),要求出两个起点到kfc最短的时间,移动到上下左右相邻结点要花的时间是11(为啥是11,是不是出题人单身太久了)。题目保证一定有解

题解

又是bfs,bfs,bfs。。。从两个点分别做一次bfs,要注意两个人不是同时出发的,到达时间是两个人所花时间之和。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
import java.util.*;

class Point {
int x, y, step;

public Point(int x, int y, int step) {
this.x = x;
this.y = y;
this.step = step;
}

public Point(int x, int y) {
this.x = x;
this.y = y;
}

public Point(Point point) {
this.x = point.x;
this.y = point.y;
this.step = point.step;
}
}

public class Main {

static int[] dx = {1, -1, 0, 0};
static int[] dy = {0, 0, 1, -1};

static char[][] mp = new char[205][205];
static boolean[][] vis = new boolean[205][205];
static int[][] KFC = new int[205][205];//记录每个kfc的时间

public static void main(String[] args) {
Scanner cin = new Scanner(System.in);

while (cin.hasNextInt()) {
int n = cin.nextInt(), m = cin.nextInt();
int ans = Integer.MAX_VALUE;
int yx = 0, yy = 0, mx = 0, my = 0;

String s = cin.nextLine();
Queue<Point> queue = new LinkedList<Point>();
for (int i = 0; i < n; i++) {
s = cin.nextLine();
for (int j = 0; j < s.length(); j++) {
mp[i][j] = s.charAt(j);
vis[i][j] = false;
KFC[i][j] = 0;
if (mp[i][j] == 'Y') {
yx = i;
yy = j;
}
if (mp[i][j] == 'M') {
mx = i;
my = j;
}
}
}

Point now = new Point(yx, yy, 0);
queue.offer(now);
vis[yx][yy] = true;
while (!queue.isEmpty()) {
now = queue.peek();
queue.poll();

if (mp[now.x][now.y] == '@') KFC[now.x][now.y] = now.step * 11;

for (int k = 0; k < 4; k++) {
Point next = new Point(now);
next.step++;
next.x += dx[k];
next.y += dy[k];
if (next.x >= 0 && next.x < n && next.y >= 0 && next.y < m && mp[next.x][next.y] != '#' && !vis[next.x][next.y]) {
vis[next.x][next.y] = true;
queue.offer(next);
}
}
}

for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
vis[i][j] = false;
}
}
while (!queue.isEmpty()) queue.poll();

now = new Point(mx, my, 0);
queue.offer(now);
vis[yx][yy] = true;
while (!queue.isEmpty()) {
now = queue.peek();
queue.poll();

if (mp[now.x][now.y] == '@'){
KFC[now.x][now.y] += now.step * 11;
ans = Math.min(KFC[now.x][now.y], ans);
}

for (int k = 0; k < 4; k++) {
Point next = new Point(now);
next.step++;
next.x += dx[k];
next.y += dy[k];
if (next.x >= 0 && next.x < n && next.y >= 0 && next.y < m && mp[next.x][next.y] != '#' && !vis[next.x][next.y]) {
vis[next.x][next.y] = true;
queue.offer(next);
}
}
}

System.out.println(ans);
}
}
}
Donate comment here