#JC0401. 自然数的拆分问题
利用回溯算法，每次都从1遍历到上限，并记录当前搜索的值以及总和。每当总和等于n时，输出所有记录的值。
using namespace std;
int t,n,m,a[100],ans;
string s;
int run(int l,int s,int sum)
{
if (sum==n)
{
if (s==1) return 0;
for (int i=1;i<s;i++)
cout<<a[i]<<"+";
cout<<a[s]<<endl;
return 0;
}
s++;
for (int i=l;i<=n;i++)
{
a[s]=i;
if (sum+i>n) break;
run(i,s,sum+i);
}
return 0;
}
int main()
{
cin>>n;
run(1,0,0);
return 0;
}
#JC0402. 八皇后问题
利用回溯算法，因为每行、每列、每个对角线都不能放置棋子，但是搜索时是按行从上往下，所以只需要维护三个数组，分别记录别每列、每个对角线都是否放过棋子。在放置棋子时，用x+y表示所在的右斜对角线，用x-y+n表示左斜对角线（+n是防止结果为负数，超出数组下标范围）
int n,a[20],x[20],y[20],b1[50],b2[50],ans;
int run(int i)
{
if (i==n+1)
{
ans++;
if (ans>=4) return 0;
F(j,1,n)
CO a[j] P;
CL;
return 0;
}
for (int j=1;j<=n;j++)
if (!y[j]&&!b1[i+j]&&!b2[i-j+n])
{
b1[i+j]=b2[i-j+n]=y[j]=1;
a[i]=j;
run(i+1);
b1[i+j]=b2[i-j+n]=y[j]=0;
}
return 0;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
CI n;
run(1);
CO ans L;
return 0;
}#JC0403. Lake Counting S
该题可以用多次回溯来做，每一次回溯都会找到并标记连续的W，即一个水坑里的全部W，而对每个没有被标记的W，都进行一次回溯，最后会标记完所有的W，也就找到了所有的水坑。
用数组a来表示地图，数组b来表示w是否被标记过。每次回溯时都将能找到的W在b中标记，最后再遍历数组a，结合数组b寻找没有被标记过的W，进行下一次回溯。
int n,m,ans;
int a[200][200],b[200][200];
string s;
int run(int x,int y)
{
int x1=max(1,x-1);
int y1=max(1,y-1);
int x2=min(n,x+1);
int y2=min(m,y+1);
F(i,x1,x2)
F(j,y1,y2)
{
if (i==x&&j==y) continue;
if (a[i][j]&&(!b[i][j]))
{
b[i][j]=1;
run(i,j);
}
}
return 0;
}
int main()
{
// ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
CI n>>m;
F(i,1,n)
{
CI s;
F(j,1,m)
if (s[j-1]=='W') a[i][j]=1;
}
F(i,1,n)
{
F(j,1,m)
if (a[i][j]&&(!b[i][j]))
{
run(i,j);
ans++;
}
}
CO ans L;
return 0;
}#JC0404. 拯救oibh总部
可以将地图扩展至(0,0)到(n+1,m+1)，最外面一圈填充0代表水坑，然后从坐标0,0开始，搜索连续的0并标记。最后再遍历整个地图，计数没有标记且为0的区域数量。
int n,m,a[501][501],b[501][501],ans;
char c;
int run(int x,int y)
{
if (x<0||x>n+1||y<0||y>m+1) return 0;
int zx[4]={-1,0,1,0};
int zy[4]={0,-1,0,1};
F(i,0,3)
{
if (x+zx[i]>=0&&y+zy[i]>=0&&x+zx[i]<=n+1&&y+zy[i]<=m+1)
if (!a[x+zx[i]][y+zy[i]]&&!b[x+zx[i]][y+zy[i]])
{
b[x+zx[i]][y+zy[i]]=1;
run(x+zx[i],y+zy[i]);
}
}
return 0;
}
int main()
{
// ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
CI n>>m;
F(i,1,n)
F(j,1,m)
{
CI c;
if (c=='*') a[i][j]=1;
}
run(0,0);
F(i,1,n)
F(j,1,m)
if (!b[i][j]&&!a[i][j]) ans++;
CO ans L;
return 0;
}#JC0405. Need for Pink Slips
利用回溯，每次按照题目要求调整c,m,p的概率并在选中p时统计概率。回溯时传入c,m,p的概率，当前抽奖次数，当前的总概率。
int t;
double c,m,p,v;
double ans;
string s;
int run(double c,double m,double p,double v,int t,double f)
{
if (c!=0)
{
if (c-v<=1e-6)
{
// CO "IN" L;
if (m!=0.0) run(0.0,m+c/2,p+c/2,v,t+1,f*c);
else run(0.0,0.0,1,v,t+1,f*c);
}
else
{
if (m!=0.0) run(c-v,m+v/2,p+v/2,v,t+1,f*c);
else run(c-v,0.0,p+v,v,t+1,f*c);
}
}
if (m!=0)
{
if (m-v<=1e-6)
{
if (c!=0.0) run(c+m/2,0.0,p+m/2,v,t+1,f*m);
else run(0.0,0.0,1,v,t+1,f*m);
}
else
{
if (c!=0.0) run(c+v/2,m-v,p+v/2,v,t+1,f*m);
else run(0.0,m-v,p+v,v,t+1,f*m);
}
}
if (p!=0)
{
f*=p;
t++;
ans+=t*f;
}
return 0;
}
int main()
{
// ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
CI t;
while (t--)
{
CI c>>m>>p>>v;
ans=0;
run(c,m,p,v,0,1);
printf("%.10lf\n",ans);
}
return 0;
}#JC0407. Catch That Cow S
本题利用广度优先搜索bfs，不断判断下一次移动是否会超出移动或到达已经移动过的地方，并将其加入到队列中，直到整个地图全被搜索完，然后输出牛所在的坐标的搜索深度。
int x,y,t;
struct Point
{
int x,depth;
Point(int x,int depth):x(x),depth(depth){};
};
int main()
{
// ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
CI t;
while (t--)
{
CI x>>y;
int v[MAX+10]={0};
queue<Point> q;
v[x]=1;
q.push(Point(x,0));
while (!q.empty())
{
Point p=q.front();
if (p.x==y)
{
CO p.depth L;
break;
}
if (p.x-1>=0&&!v[p.x-1])
{
q.push(Point(p.x-1,p.depth+1));
v[p.x-1]=1;
}
if (p.x+1<=MAX&&!v[p.x+1])
{
q.push(Point(p.x+1,p.depth+1));
v[p.x+1]=1;
}
if (p.x*2<=MAX&&!v[p.x*2])
{
q.push(Point(p.x*2,p.depth+1));
v[p.x*2]=1;
}
q.pop();
}
}
return 0;
}#JC0408. 马的遍历
本体利用dfs，不断判断下一次马移动是否会超出移动或到达已经移动过的地方，并将其加入到队列中，直到整个地图全被搜索完，然后输出每个坐标的搜索深度。
int v[MAX+10][MAX+10]={-1,-1};
int n,m,x,y;
int f[8][2]={{-2,-1},{-1,-2},{-2,1},{-1,2},{1,-2},{2,-1},{1,2},{2,1}};
struct Point
{
int x,y,depth;
Point(int x,int y,int depth):x(x),y(y),depth(depth){};
};
queue<Point> q;
int main()
{
// ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
CI n>>m>>x>>y;
q.push(Point(x,y,0));
F(i,1,n)
{
F(j,1,m)
v[i][j]=-1;
}
v[x][y]=0;
while (!q.empty())
{
Point p=q.front();
F(i,0,7)
{
if (p.x+f[i][0]>=1&&p.x+f[i][0]<=MAX&&p.y+f[i][1]>=1&&p.y+f[i][1]<=MAX&&v[p.x+f[i][0]][p.y+f[i][1]]==-1)
{
q.push(Point(p.x+f[i][0],p.y+f[i][1],p.depth+1));
v[p.x+f[i][0]][p.y+f[i][1]]=p.depth+1;
}
}
q.pop();
}
F(i,1,n)
{
F(j,1,m)
CO v[i][j]<<"\t";
CL
}
return 0;
}
Comments | NOTHING