[做题] 2022.3.28 穿越雷区+分巧克力

雷区+分巧克力"/>

[做题] 2022.3.28 穿越雷区+分巧克力

#include<iostream>
#include<memory.h>
using namespace std;
const int maxn = 10000;
int hiwi[maxn+10][2]; //[][0]为高[][1]为宽 存放不同饼干长宽 
int cookie[maxn+10][(maxn+10)/2];    //-1 不存在 0 未分饼干 1已分饼干 
int N,K;//N块 K人
bool ok; //终止信号 (最优解) 
int total; //第n块饼干
void dps(int x,int y,int hw) //参数1 2饼干坐标 参数3 长宽 
{   for(int k=x;k<x+hw;k++){for(int j=y;j<y+hw;j++){if(cookie[k][j]==0) cookie[k][j]=1;else return;}}total++;if(total==K) {ok=1;return ;}if(y+hw*2<=hiwi[N][1]) dps(x,y+hw,hw);if(x+hw*2<=hiwi[N][0]) dps(x+hw,y,hw); else if(y==0){x=hiwi[N][0];y=0;N++;hiwi[N][0]+=hiwi[N-1][0];dps(x,y,hw);};}
int main(void)
{   int i,x;int hw=1;//分的饼干长度 x=0;memset(cookie,-1,sizeof(cookie));cin>>N>>K;for(i=1;i<=N;i++){cin>>hiwi[i][0];cin>>hiwi[i][1];}N=1;//配合后续dfs调用 for(int k=1;k<i;k++){   int length=hiwi[k][0]+x;for(;x<length;x++){for(int y=0;y<hiwi[k][1];y++){cookie[x][y]=0;}}}//至此，cookie数组完成，开始寻找策略  while(1){ok=0;dps(0,0,hw); if(ok) hw++;else break;}//至此，最优解寻找完毕 cout<<hw;
} 

关于分巧克力，我硬是用二维数组用一个伪dps实现，一个正方形一个正方形来找（安慰自己：我的二维数组使问题解决可视化了），结果oj上显示运行错误，猜想是二维数组不能承受100000的数据量导致数组越界了。

所以我需要找更好的方法。

根据题解，发现暴力枚举+二分的思路和上面的算法简直天差地别——我忽略了一个重要关系：

一个饼干被正方形划分的个数 n =h*w/ x^2  即饼干面积除以正方形面积 （贻笑大方了）

不过要注意的是，直接这样写会造成只考虑面积，忽视单边边长限制而导致有些情况不存在。

所以考虑到单位边长，算式改为 n = (h/x)*(w/x)

所以算法的重要性直接凸显出来了。

#include<iostream>
using namespace std;
const int maxn=100000;
int hiwi[maxn][2]; //0为宽 1为高 
int l=1,r=100000; //二分枚举端点 
int n,k;
bool judge(int m)
{   int num=0;for(int i=0;i<n;i++){num+=(hiwi[i][0]/m)*(hiwi[i][1]/m);}if(num>=k) return true;else return false;}
int main(void)
{   cin>>n>>k;for(int i=0;i<n;i++){cin>>hiwi[i][0]>>hiwi[i][1];}while(l<r){   int m=(l+r+1)>>1; //注意这个加一，四舍五入取大。 if(judge(m)) l=m;else r=m-1;}cout<<l;
}

————————————————————————

穿越雷区

#include<bits/stdc++.h>
using namespace std;
int m,n,k,j,ok=1;
char room[100][100];
int color[100][100]; 
void dp(int x,int y)
{   if(room[x][y]=='B'){k=x;j=y;ok=0;}  //只在两种情况下继续： 1.未曾走过 2.走过且比当前路程更好if(room[x+1][y]!=room[x][y]&&x+1<n){if(color[x+1][y]==-1) {color[x+1][y]=color[x][y]+1;dp(x+1,y);}else if(color[x][y]+1<color[x+1][y]) {color[x+1][y]=color[x][y]+1;dp(x+1,y);}}		if(room[x-1][y]!=room[x][y]&&x-1>=0){if(color[x-1][y]==-1) {color[x-1][y]=color[x][y]+1;dp(x-1,y);}else if(color[x][y]+1<color[x-1][y]){color[x-1][y]=color[x][y]+1;dp(x-1,y);}}if(room[x][y+1]!=room[x][y]&&y+1<n){if(color[x][y+1]==-1) {color[x][y+1]=color[x][y]+1;dp(x,y+1);}else if(color[x][y]+1<color[x][y+1]) {color[x][y+1]=color[x][y]+1;dp(x,y+1);}}if(room[x][y-1]!=room[x][y]&&y-1>=0){if(color[x][y-1]==-1) {color[x][y-1]=color[x][y]+1;dp(x,y-1);}else if(color[x][y]+1<color[x][y-1]) {color[x][y-1]=color[x][y]+1;dp(x,y-1);}}
} 
int main(void)
{  cin>>n;int x,y;for(int i=0;i<n;i++){for(int j=0;j<n;j++){char c;cin>>c;if(c=='A') {x=i;y=j;}room[i][j]=c;}}memset(color,-1,sizeof(color));color[x][y]=0;dp(x,y);if(ok) cout<<-1;	else cout<<color[k][j];return 0;
}

用的类似dp的方法。以最优子解推最优终解

实际上这题的常见思路是bfs。

#include<iostream>//ps:此题队列均从1开始。除了那个next方向 
using namespace std;
struct node{int x,y,steps; //x y定位node坐标 char flag;    //step记录步数 flag确认 雷区符号 
};
char mmap[110][110]; //地图 
bool book[110][110]; //导航 
int next[4][2]={{0,1},{0,-1},{-1,0},{1,0}}; //方向 
node nod[1000];//bfs队列 
bool ok=false;
int main(void)
{   int n;cin>>n;int ax,ay;//接收A点坐标（即起始坐标） int head,tail;head=tail=1;//bfs 队列初始化 for(int x=1;x<=n;x++){for(int y=1;y<=n;y++){cin>>mmap[x][y];if(mmap[x][y]=='A'){ax=x;ay=y;}}}nod[head].x=ax;nod[head].y=ay;nod[head].steps=0;nod[head].flag='A';book[ax][ay]=1;tail++;//bfs队列开始！ （head与tail的分离即结点的衍生） while(head!=tail){  for(int i=0;i<4;i++){//四方向 //给模拟的 tx ty 赋值判断该方向是否可行 int tx,ty;tx=nod[head].x+next[i][0];ty=nod[head].y+next[i][1];if(tx>n) continue;if(ty>n) continue;//判断衍生结点是否满足题意（+-相间 且曾走过） if(mmap[tx][ty]!=nod[head].flag&&book[tx][ty]==0){ book[tx][ty]=1;//满足题意，开始保留结点信息，准备下一次 nod[tail].x=tx;nod[tail].y=ty;nod[tail].steps=nod[head].steps+1;nod[tail].flag=mmap[tx][ty];tail++;}}if(nod[head].flag=='B'){ok=true;cout<<nod[head].steps;break;}head++;}if(!ok) cout<<"-1";
}