华容道70
设两个变量，记在一个结构体里
在进行爆搜，就是一个普通的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#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
using namespace std;
int n,m,k;
struct stu{
int x,y,x1,y1,s;
};
int f[31][31][31][31];
int x[4]={
1,-1,0,0};
int y[4]={
0,0,1,-1};
int a[39][39];
int bfs(stu p,int x2,int y2)
{
queue<stu> q;
q.push(p);
memset(f,0,sizeof(f));
f[p.x][p.y][p.x1][p.y1]=1;
while(!q.empty())
{
stu o=q.front();q.pop();
if(o.x1==x2&&o.y1==y2)
return o.s;
for(int i=0;i<=3;i++)
{
stu tmp;
tmp.x=o.x+x[i];
tmp.y=o.y+y[i];
if(o.x1==tmp.x&&o.y1==tmp.y)
{
tmp.x1=o.x;
tmp.y1=o.y;
}
else
{
tmp.x1=o.x1;
tmp.y1=o.y1;
}
tmp.s=o.s+1;
if(tmp.x<1||tmp.y<1||tmp.x>n||tmp.y>m||!a[tmp.x][tmp.y]) continue;
if(!f[tmp.x][tmp.y][tmp.x1][tmp.y1])
{
q.push(tmp);
f[tmp.x][tmp.y][tmp.x1][tmp.y1]=1;
}
}
}
return -1;
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
for(int i=1;i<=k;i++)
{
stu p;int x2,y2;
scanf("%d%d%d%d%d%d",&p.x,&p.y,&p.x1,&p.y1,&x2,&y2);
p.s=0;
printf("%d\n",bfs(p,x2,y2));
}
}
生日蛋糕
进行dfs
起始条件为最大的半径和高，枚举他们，再加一系列剪枝
1.如果当时的面积大于最优解，返回
2.如果所有的体积加起来都不够v，返回
3.如果加上最小的体积都比v大，返回
1 | #include<cstdio> |