关于昨天搜索考试的题目考察内容大体如下:
1.有重复元素的排列问题
dfs + STL大法(去重)
2.烈火金刚
bfs板子题
3.剪纸
记忆化搜索
4.玛丽有只小羔羊
二分 + bfs
难度排序
1 < 2 < 3 < 4
1.有重复元素的排列问题
此题可以用STL模板自带的去重完成,其思想和全排列类似
上代码
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
char a[505], b[505];//一个输入,一个存储
int n, sum = 1;//先初始化1,因为字符串本身算一种
void intn();//输入
void dfs();//搜索
int main() {
intn();
dfs();
return 0;
}
void intn() {
// freopen("perm.in","r",stdin);这题目有毒啊
// freopen("perm.put","w",stdout);
scanf("%d", &n);
scanf("%s", a);
sort(a, a+n);
strcpy(b, a);
}
void dfs() {
printf("%s\n", a);
while(next_permutation(a, a+n)) {//STL自动去重
if(!strcmp(b, a)) continue;
printf("%s\n", a);
sum ++;
}
printf("%d",sum);
}
2.烈火金刚
bfs的板子题,但是要注意输入用字符,因为每个数字之间没有空格,%d会很自然的将一排数都读在一起,于是,输入就成功地出锅了…
关于输入,如果要一个一个字符输的话,建议用cin,不能用scanf("%c"),否则就用字符串输入:scanf("%s"),但是也要注意用它会从0号位开始存.
#include <cstdio>
#include <iostream>
#include <queue>
using namespace std;
const int MAXN = 1005;
const int INF = 0x3f3f3f3f;//极值
int dx[8] = {0, 1, 0, -1};//方向数组x
int dy[8] = {1, 0, -1, 0};//方向数组y
struct note {
int x, y;//坐标
};
int n, m;
char mp[MAXN][MAXN];//商城地图
int ans[MAXN][MAXN];//答案数组
int sx, sy;//初始坐标
int gx, gy;//终点坐标
int bfs();
void intn();
int main() {
intn();
printf("%d", bfs());
return 0;
}
void intn() {//初始化 + 输入
scanf("%d", &n);//读入 边长
m = n;
for(int i = 1; i <= n; i ++) {//读入商场地图
for(int j = 1; j <= m; j ++) {
cin>>mp[i][j];
}
}
scanf("%d %d %d %d", &sx, &sy, &gx, &gy);
for(int i = 0; i <= n; i ++) {//答案数组初始化
for(int j = 0; j <= m; j ++) {
ans[i][j] = INF;
}
}
}
int bfs() {
queue<note> q;
ans[sx][sy] = 0;//初始化
note a, b;//定义
a.x = sx;
a.y = sy;
q.push(a);//起点入队
while(q.size()) {
a = q.front();//枚举当前地点
q.pop();//弹出没用的地点
if(a.x == gx && a.y == gy) {//到达目的地就跳出循环
break;
}
for(int i = 0;i <= 3;i ++) {//枚举四种走法
int nx = a.x + dx[i];//当前坐标
int ny = a.y + dy[i];
if(nx >= 0 && nx <= n && ny >=0 && ny <= m && mp[nx][ny] != '1' && ans[nx][ny] == INF) {//判断是否越界
b.x = nx;
b.y = ny;
q.push(b);//入队
ans[nx][ny] = ans[a.x][a.y] + 1;//更新答案步数
}
}
}
return ans[gx][gy];//返回
}
3.剪纸
请注意 本题需要用 记忆化搜索 是有 明显提示的(注意我加粗的地方):
【样例1解释】
对于样例1中的第一组操作（2 2 1）
需要进行如下操作：
1、将22的蜡光纸剪成21，代价是2^2=4
2、将21的蜡光纸剪成11，代价是1^2=1
最小代价为：22+12=5
如果有小朋友想问样例第二组数据3怎么得到5的，由于必须剪断，所以得到面积1的代价**+得到 面积2 的代价就是5，清楚了吧~
【数据规模与说明】
1≤t≤40910**(这么多组,利用前面的结果求解果,可以利用前面的数据求结果)
1≤n,m≤30,1≤p≤min(n*m,50)
#include <cstdio>
#include <iostream>
using namespace std;
int sum[35][35][55], ans;//sum[35][35][55]用作储存结果
int p, m, n, t;
int dfs(int n, int m, int p);
void work();
int main() {
work();
return 0;
}
void work() {
scanf("%d", &t);
while (t--) {
scanf("%d %d %d", &m, &n, &p);
if (m > n)//横着剪与竖着减结果一样
swap(n, m);
printf("%d\n", dfs(m, n, p));
}
}
int dfs(int n, int m, int p) {
if (n * m == p || p == 0)//特判 1.当p的面积等于了n * m的面积
return 0;//或者 p的面积本身为零, 就不用剪
if (sum[n][m][p]) //算过(记忆化的好处)
return sum[n][m][p];
int ans = 0x3f3f3f3f;//赋极值(对了,不能用INT_MAX, WJC已经用血的教训告诉我们,Ta很容易溢出)
for (int i = 1; i <= n / 2; i++) {//剪一刀,少一半 横着剪
for (int j = 0; j <= p; j++) {
ans = min(ans, dfs(i, m, j) + dfs(n - i, m, p - j) + m * m);//更新
}
}
for (int i = 1; i <= m / 2; i++) {//剪一刀,少一半 竖着剪
for (int j = 0; j <= p; j++) {
ans = min(ans, dfs(n, i, j) + dfs(n, m - i, p - j) + n * n);//更新
}
}
return sum[n][m][p] = ans;返回
}
4.玛丽有只小羔羊
这道题题面告诉我,是玛丽找羊,我就被骗了…
正解应该是羊找玛丽
why?
because
羊的位置是固定的,它只有一个点,而玛丽初始位置在第一层,并且第一层全是平台,可以随处走动,只要搜到了地面,就可以结束了,而玛丽需要枚举多个点,过程麻烦得多,于是我就 Runtime Error
然后,玛丽也迷路了…
此题最重要的是要二分和宽搜一起用,搜索的终点就是地面，搜到地面后，就结束搜索,考试时,没有想出来,gm讲解后我又打了一份;
#include <cstdio>
#include <queue>
#include <cstring>
#include <iostream>
using namespace std;
int n, m, x1, y1;
bool a[55][55], falg[55][55];
struct cjg {
int r, c;
} t1, t2, t3;
queue<cjg> q;
bool bfs(int x);
int ef(int l, int r);
int main() {
char k;
scanf("%d %d", &m, &n);
for (int i = 1; i <= m; ++i) {
scanf("%*c");//过滤字符
for (int j = 1; j <= n; ++j) {
cin >> k;
if (k == '.')
a[i][j] = 0;//0 -> 不能走
else
a[i][j] = 1;//1 -> 能走
}
}
scanf("%d %d", &x1, &y1);//小羔羊的坐标
if (x1 == m) {//特判 羊和玛丽在一层...
printf("0\n");
return 0;
}
int ans = ef(1, m - x1);
printf("%d\n", ans);
return 0;
}
int ef(int l, int r) {//二分
while (l <= r) {
int mid = (l + r) / 2;//枚举梯子长度
if (bfs(mid) && !bfs(mid - 1))//梯子再短一丢丢就不行了
return mid;//返回答案
else if (bfs(mid))//梯子行,但是还有更好的答案
r = mid;
else
l = mid + 1;//同上
}
}
bool bfs(int x) {
while (!q.empty()) q.pop();//清零
memset(falg, 0, sizeof(falg));//清零
falg[x1][y1] = 1;//入队
t1.r = x1;
t1.c = y1;
q.push(t1);//入队
while (!q.empty()) {//不为空就继续搜
t2 = q.front();
q.pop();
t3 = t2;
t3.c = t2.c + 1;//向右走
if (a[t3.r][t3.c] && !falg[t3.r][t3.c]) {//判断边界
falg[t3.r][t3.c] = 1;//标记
q.push(t3);//入队
}
t3 = t2;//重新赋值
t3.c = t2.c - 1;//向左走
if (a[t3.r][t3.c] && !falg[t3.r][t3.c]) {//判断边界
falg[t3.r][t3.c] = 1;//标记
q.push(t3);//入队
}
for (int i = 1; i <= x; i++) {//往上走
if (!falg[t2.r - i][t2.c] && a[t2.r - i][t2.c]) {
t3 = t2;
t3.r = t2.r - i;
falg[t3.r][t3.c] = 1;//标记
q.push(t3);//入队
break;
}
}
for (int i = 1; i <= x; i++) {//往下走
if (!falg[t2.r + i][t2.c] && a[t2.r + i][t2.c]) {
t3 = t2;
t3.r = t2.r + i;
if (t3.r == m)
return 1;
falg[t3.r][t3.c] = 1;//标记
q.push(t3);//入队
break;
}
}
}
return 0;//四个方向都不行,返回0
}
京公网安备 11010502036488号