给定一个字符串，以中心对称左右字母分别比较大小，如果左边大于右边则对调，如最后一位有符号保持该位不变。
例如：输入：goxd！
输出：doxg！
参考如下：
#include <stdio.h>
#include <string.h>
int main()
{
char str[100];
scanf("%s", str);
int length = strlen(str);
int left = 0, right = length - 2;
while (left < right)
{
if (str[left] > str[right]) // 如果左边大于右边，则互换
{
char temp = str[left];
str[left] = str[right];
str[right] = temp;
}
left++;
right--;
}
printf("%s", str);
return 0;
}
这道题是一道典型的搜索题，我们要求的是机器人数最少，所以我们可以考虑使用广度优先搜索。
具体而言，我们可以用一个队列来存储从起点开始生成的各种状态，每次从队列的头部取出一个状态进行扩展，扩展的方法有：
在当前点的下方加一个机器人；
把一个机器人放在当前点；
在当前点的右边加一个机器人。
若当前状态生成的新状态中没有被观察的位置，就说明可以监视所有的空间。在这种情况下，我们就可以统计当前状态机器人的数量并进行比较，找到最少需要的机器人数量。如果后续状态的机器人数量已经大于等于当前的最小值了，那么我们就不用再生成这个状态了，因为它一定不是我们需要的最优解。
首先，要定义一个搜索中使用的节点结构体 Node，它存储了当前已经监控到的房间情况，当前机器人的位置以及机器人数和被监控的房间数。
优先队列 q 的定义可以参照下面这样，需要重载 cmp 函数，保证被监控的房间数较小的节点有更高的优先级（即越先被访问到表示他是最优解）。注意 Node 中的其他属性需要按字母顺序，通过结构体的默认排序来排序。
//优先队列，cmp函数会自动执行
priority_queue<Node, vector<Node>, cmp> q;
// 优先队列的比较函数重写
struct cmp
{
bool operator() (Node a, Node b)
{
// 比较哪个快照被监视房间多（小顶堆）
return a.roomNum > b.roomNum;
}
};
struct Node{
// 机器人位置
int robot_position[30][30];
// 被监视的房间位置
int room_watched[30][30];
// (i,j)为当前遍历到的坐标
int i,j;
// 机器人数 被监视的房间个数
int robotNum,roomNum;
};
init 函数定义如下：
Node init(Node node)
{
// 初始化robot_position数组全为0
memset(node.robot_position,0,sizeof(node.robot_position));
// 初始化room_watched数组全为0
memset(node.room_watched,0,sizeof(node.room_watched));
// 当前点在i=1,j=1
node.i=1;node.j=1;
// 当前的机器人数；当前的监控房间数
node.robotNum=0;node.roomNum=0;
// 在博物馆的上下扩充两行
for(int i=0;i<=m+1;i++)
node.room_watched[i][0]=node.room_watched[i][m+1]=1;
// 在博物馆的左右扩充两列
for(int i=0;i<=n+1;i++)
node.room_watched[0][i]=node.room_watched[n+1][i]=1;
return node;
}
setRobot 函数定义如下：
void setRobot(Node p,int x,int y)
{
// 以下几行都是在复制一份快照p
Node node;
node=init(node);
node.i=p.i;
node.j=p.j;
node.roomNum=p.roomNum;
memcpy(node.robot_position, p.robot_position, sizeof(p.robot_position));
memcpy(node.room_watched, p.room_watched, sizeof(p.room_watched));
// 在（x,y)点新增机器人，机器人数量要+1
node.robot_position[x][y]=1;
node.robotNum=p.robotNum+1;
// 对这个新增机器人的上下左右和自身标记被监控
for(int d=0;d<5;d++)
{
// pos_x,pos_y表示机器人上下左右位置，我们标记这些位置的房间被监控
int pos_x=x+position[d][0];
int pos_y=y+position[d][1];
node.room_watched[pos_x][pos_y]++;
// 标记一个房间，roomNum就加一。
// 一定要等于1，因为有的房间会被重复监控，那就是2了
if(node.room_watched[pos_x][pos_y]==1)
{
node.roomNum++;
}
}
// 如果行数不越界 且 当前点被监控了
while(node.i<=m && node.room_watched[node.i][node.j])
{
// 当前点的列右移一个单位
node.j++;
// 如果右移之后越界了，就换行
if(node.j>n)
node.i++,node.j=1;
}
// 把当前快照存到优先队列里，会调用cmp排序，保证最顶端的是最优的快照
q.push(node);
return;
}
最后，我们只需要进行广度优先搜索，并将答案打印即可：
int main()
{
scanf("%d%d",&m,&n);
ans=m*n/3+2; // 机器人最多的数量
Node node;
node=init(node);
q.push(node);
while(!q.empty())
{
Node p=q.top();
q.pop();
if(p.roomNum < m*n)
{
if(p.i<m) setRobot(p,p.i+1,p.j);
if((p.i==m && p.j==n) || p.room_watched[p.i][p.j+1]==0) setRobot(p,p.i,p.j);
if(p.j<n && (p.room_watched[p.i][p.j+1]==0 || p.room_watched[p.i][p.j+2]==0)) setRobot(p,p.i,p.j+1);
}
else(p.roomNum>=m*n)
{
if(p.robotNum<ans)
{
ans=p.robotNum;
memcpy(ans_arr, p.robot_position, sizeof(p.robot_position));
}
}
}
printf("%d\n",ans);
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
printf("%d ",ans_arr[i][j]);
printf("\n");
}
return 0;
}
给定一个字符串，以中心对称左右字母分别比较大小，如果左边大于右边则对调，如最后一位有符号保持该位不变。
例如：输入：goxd！
输出：doxg！
参考如下，注意大写字母也被包括在字母里
#include<stdio.h>
#include<string.h>
int main()
{
char s[100]={'\0'};
int l,i;
char ret;
gets(s);
l=strlen(s);
if((s[l-1]>='a'&&s[l-1]<='z')||(s[l-1]>='A'&&s[l-1]<='Z')){
for(i=0;i<l/2;i++){
if(s[i]>s[l-i-1]){
ret=s[i];
s[i]=s[l-i-1];
s[l-i-1]=ret;
}
}
}else{
for(i=0;i<(l-1)/2;i++){
if(s[i]>s[l-i-2]){
ret=s[i];
s[i]=s[l-i-2];
s[l-i-2]=ret;
}
}
}
puts(s);
return 0;
}