题一：
/*
数论中有著名的四方定理：所有自然数至多只要用四个数的平方和就可以表示。
我们可以通过计算机验证其在有限范围的正确性。
对于大数，简单的循环嵌套是不适宜的。下面的代码给出了一种分解方案。
请仔细阅读，填写空缺的代码（下划线部分）。
注意：请把填空的答案（仅填空处的答案，不包括题面）存入考生文件夹下对应题号的“解答.txt”中即可。
直接写在题面中不能得分。
*/
#include <iostream>
#include <math.h>
using namespace std;
int f(int n, int a[], int idx)
{
if(n == 0) return 1; // 填空1
if(idx==4) return 0;
for(int i=(int)sqrt(n * 1.0); i>=1; i--)
{
a[idx] = i;
if(f(n - a [idx] * a[idx],a,idx + 1)) return 1; // 填空2
}
return 0;
}
int main(int argc, char* argv[])
{
for(;;)
{
int number;
printf("输入整数(1~10亿)：");
scanf("%d",&number);
int a[] = {0,0,0,0};
int r = f(number, a, 0);
printf("%d: %d %d %d %d\n", r, a[0], a[1], a[2], a[3]);
}
return 0;
}
题二：
/*
在对文本进行简单加密的时候，可以选择用一个n位的二进制数，对原文进行异或运算。
解密的方法就是再执行一次同样的操作。
加密过程中n位二进制数会循环使用。并且其长度也可能不是8的整数倍。
下面的代码演示了如何实现该功能。
请仔细阅读，填写空缺的代码（下划线部分）。
注意：请把填空的答案（仅填空处的答案，不包括题面）存入考生文件夹下对应题号的“解答.txt”中即可。
直接写在题面中不能得分。
*/
#include <iostream>
using namespace std;
void f(char* buf, unsigned char* uckey, int n)
{
int i;
for(i=0; i<n; i++)
buf[i] = buf[i] ^ uckey[i];
}
int main(int argc, char* argv[])
{
char p[] = "abcd中国人123"; // 待加密串
char* key = "11001100010001110"; //以串的形式表达的密匙，运算时要转换为按位存储的形式。
int np = strlen(p);
int nk = strlen(key);
unsigned char* uckey = (unsigned char*)malloc(np);
// 密匙串需要按位的形式循环拼入 uckey中
int i;
for(i=0; i<np*8; i++)
{
if(key[i%nk]=='1')
{
uckey[i / 8] = (uckey[i / 8] << 1) | 0x01; // 填空1
//uckey[i/8] |= (unsigned char)0x80 >> (i%8); //标准答案
}
else
{
uckey[i / 8] = uckey[i / 8] << 1; // 填空2
//uckey[i/8] &= ~((unsigned char)0x80 >> (i%8)); //标准答案
}
}
for(i=0; i<np; i++)
{
printf("%02X ", (unsigned char)uckey[i]);
}
printf("\n");
f(p, uckey, strlen(p));
for(i=0; i<np; i++)
{
printf("%02X ", (unsigned char)p[i]);
}
printf("\n");
f(p, uckey, strlen(p));
printf("%s\n", p);
free(uckey);
return 0;
}
题三：
/**
为什么1小时有60分钟，而不是100分钟呢？这是历史上的习惯导致。
但也并非纯粹的偶然：60是个优秀的数字，它的因子比较多。
事实上，它是1至6的每个数字的倍数。即1,2,3,4,5,6都是可以除尽60。
我们希望寻找到能除尽1至n的的每个数字的最小整数。
不要小看这个数字，它可能十分大，比如n=100, 则该数为：
69720375229712477164533808935312303556800
请编写程序，实现对用户输入的 n （n<100）求出1~n的最小公倍数。
例如：
用户输入：
6
程序输出：
60
用户输入：
10
程序输出：
2520
要求考生把所有函数写在一个文件中。调试好后，存入与考生文件夹下对应题号的“解答.txt”中即可。
相关的工程文件不要拷入。
对于编程题目，要求选手给出的解答完全符合ANSI C标准，不能使用c++特性；
不能使用诸如绘图、中断调用等硬件相关或操作系统相关的API。
*/
#include <iostream>
#include <iomanip>
using namespace std;
#define N 20
const int base = 10000;
const int width = 4;
struct Bint
{
int ln;
int v[N];
Bint()
{
ln = 0;
v[ln++] = 1;
}
};
Bint& operator*(Bint& left,const int& num)
{
int lv = 0;
for (int i = 0;i < left.ln;i++)
{
lv = left.v[i] * num + lv;
left.v[i] = lv % base;
lv /= base;
}
while (lv > 0)
{
left.v[left.ln++] = lv % base;
lv /= base;
}
return left;
}
ostream& operator << (ostream& ost,const Bint& bint)
{
if (bint.ln == 0)
{
ost << 0 << endl;
}
else
{
ost << bint.v[bint.ln - 1];
}
for (int ln = bint.ln - 2;ln >= 0;ln --)
{
ost << setw(4) << setfill('0') << right << bint.v[ln];
}
return ost;
}
int main()
{
int n = 0;
int val[102];
while ( cin >> n,n != 0)
{
memset(val,0,sizeof(val));
for (int i = 0;i <= n;i++)
{
val[i] = i;
}
for (int i = 2;i <= n;i ++)
{
for (int j = i + 1;j <= n;j++)
{
if (val[j] % val[i] == 0)
{
val[j] /= val[i];
}
}
}
Bint num;
for (int i = 2;i <= n;i++)
{
if (val[i] != 0)
{
num = num * val[i];
}
}
cout << num << endl;
}
return 0;
}
题四：
/*
为解决交通难题，某城市修建了若干条交错的地铁线路，线路名及其所属站名如stations.txt所示。
线1
苹果园
....
四惠东
线2
西直门
车公庄
....
建国门
线4
....
其中第一行数据为地铁线名，接下来是该线的站名。
当遇到空行时，本线路站名结束。
下一行开始又是一条新线....直到数据结束。
如果多条线拥有同一个站名，表明：这些线间可以在该站换车。
为引导旅客合理利用线路资源，解决交通瓶颈问题，该城市制定了票价策略：
1. 每条线路可以单独购票，票价不等。
2. 允许购买某些两条可换乘的线路的联票。联票价格低于分别购票。
单线票价和联合票价如 price.txt 所示。
线1 180
.....
线13 114
线1,线2 350
线1,线10 390
.....
每行数据表示一种票价
线名与票价间用空格分开。如果是联票，线名间用逗号分开。
联票只能包含两条可换乘的线路。
现在的问题是：根据这些已知的数据，计算从A站到B站最小花费和可行的换乘方案。
比如，对于本题目给出的示例数据
如果用户输入：
五棵松,奥体中心
程序应该输出：
-(线1,线10)-线8 = 565
如果用户输入：
五棵松,霍营
程序应该输出：
-线1-(线4,线13) = 440
可以看出，用户输入的数据是：起始站，终到站，用逗号分开。
程序输出了购票方案，在括号中的表示联票，短横线(-)用来分开乘车次序。
等号后输出的是该方案的花费数值。
请编程解决上述问题。
注意：
1. 我们测试您的程序时，所用数据与题目中的示例数据不同，但格式完全一样。
2. 当多个方案有相同的最小花费，输出任意一个方案即可。
要求考生把所有函数写在一个文件中。调试好后，存入与考生文件夹下对应题号的“解答.txt”中即可。
相关的工程文件不要拷入。
对于编程题目，要求选手给出的解答完全符合ANSI C标准，不能使用c++特性；
不能使用诸如绘图、中断调用等硬件相关或操作系统相关的API。
*/
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <map>
using namespace std;
class SubWay
{
public:
typedef vector<int> BestWay;
/**
*
**/
SubWay()
{
/*所有的id都从0开始，因为价格表的0处要求存放其单线路价格*/
way_size = 1;
station_size = 1;
/*0处保留*/
WayRoute way_route;
way_table.push_back(way_route);
/*0处保留*/
StationWayEntry station_way;
station_table.push_back(station_way);
best_price = 0x3f3f3f3f;
return;
}
/**
*
**/
~SubWay()
{
return;
}
virtual void read_station(fstream& fstr)
{
string t_station_name;
string t_way_name;
while (!fstr.eof())
{
/*读取线路名*/
getline(fstr,t_way_name);
if (fstr.eof() == true || t_way_name.empty())
{
break;
}
way_name[way_size] = t_way_name;
way_id[t_way_name] = way_size;
way_size += 1;
WayRoute t_way_route;
way_table.push_back(t_way_route);
t_way_name.clear();
/*读取站名*/
while (getline(fstr,t_station_name) && t_station_name.empty() == false)
{
/*在这里建立起路线到所经过站的表及所经过站到路线的表*/
int s = station_id[t_station_name];
if (s == 0)
{
StationWayEntry new_station;
new_station.push_back(way_size - 1);
station_table.push_back(new_station);
way_table[way_size - 1].push_back(station_size);
station_id[t_station_name] = station_size++;
}
else
{
way_table[way_size - 1].push_back(s);
station_table[s].push_back(way_size - 1);
}
t_station_name.clear();
}
}
reserve_space();
return;
}
virtual void read_price(fstream& fstr)
{
init_price_table();
while(1)
{
char ch = 0;
string way_name_first;
string way_name_second;
int t_price = 0;
while(fstr.get(ch) && ch != ',' && ch != ' ')
{
way_name_first += ch;
}
if(way_name_first.empty())
{
break;
}
/*begin read second station name*/
if(ch == ',')
{
while(fstr.get(ch) && ch != ' ')
{
way_name_second += ch;
}
}
/*begin read the price*/
if(ch == ' ')
{
while(fstr.get(ch) && ch != '\n')
{
t_price *= 10;
t_price += ch - '0';
}
}
int way_fist_id = way_id[way_name_first];
int way_second_id = 0;
if (way_name_second.empty() == false)
{
way_second_id = way_id[way_name_second];
}
price_table[way_fist_id][way_second_id] = t_price;
price_table[way_second_id][way_fist_id] = t_price;
}
return;
}
inline int get_station_size()
{
return station_size;
}
inline int get_way_size()
{
return way_size;
}
/**
* 深度优先搜索最优路径
*/
void search_best_way(string& from_name,string& to_name)
{
reset();
int from_id = station_id[from_name];
int to_id = station_id[to_name];
if (from_id == 0)
{
cout << "源地址找不到" << endl;
}
if (to_id == 0)
{
cout << "目的地找不到" << endl;
}
BestWay t_best_way(get_way_size());
dfs_best_way(from_id,to_id,t_best_way,0);;
output_best_way();
return;
}
/**
* 重新初始化状态
*/
void reset()
{
best_price = 0x3f3f3f3f;
best_way.resize(way_size);
return;
}
void output_best_way()
{
BestWay no_use_pre(best_way_size);
BestWay use_pre(best_way_size);
BestWay way_route(best_way_size);
int temp_stat = best_way[0];
int temp_stat2 = 0;
/*重新对其计算路线*/
for (int i = 1;i < best_way_size;i++)
{
temp_stat = best_way[i];
temp_stat2 = best_way[i - 1];
no_use_pre[i] = min(no_use_pre[i - 1],use_pre[i - 1]) + price_table[temp_stat][0];
if (price_table[temp_stat2][temp_stat] != 0)
{
use_pre[i] = no_use_pre[i - 1] - price_table[temp_stat2][0] + price_table[temp_stat][temp_stat2];
}
else
{
use_pre[i] = no_use_pre[i - 1] + price_table[temp_stat][0];
}
}
/*从最后一站倒退上来，记录路径，这里也可以使用递归进行实现*/
int i = best_way_size - 1;
way_route[i] = 1; /*走1路*/
for (;i > 0;i--)
{
if (way_route[i] == 1)
{
if ( no_use_pre[i] > use_pre[i])
{
way_route[i - 1] = 2;
}
else
{
way_route[i - 1] = 1;
}
}
else
{
way_route[i - 1] = 1;
}
}
for (int i = 0; i < best_way_size;i++)
{
if (way_route[i] == 2)
{
cout << "-(" << way_name[best_way[i]]
<< ","
<< way_name[best_way[i + 1]]
<< ")";
i += 1;
}
else
{
cout << "-" << way_name[best_way[i]];
}
}
cout << " = " << best_price << endl;
return;
}
protected:
/*因为访问标志位及其它一些空间为初始化，我们需要对其初始化*/
void reserve_space()
{
b_station_visit.resize(get_station_size());
b_way_visit.resize(get_way_size());
}
/**
* 初始化价格表,为价格表预留空间
*/
void init_price_table()
{
price_table.resize(get_way_size());
for (int i = 0;i < price_table.size();i++)
{
price_table[i].resize(get_way_size());
}
return;
}
/**
* 深度优先搜索最优路径
*/
void dfs_best_way(int from_id,int to_id,BestWay& cur_best_way,int off)
{
if (from_id == to_id)
{
int temp_price = calc_price(cur_best_way,off);
if (temp_price < best_price )
{
best_price = temp_price;
best_way_size = off;
for (int i = 0; i < off;i++)
{
best_way[i] = cur_best_way[i];
}
}
//output_best_way(cur_best_way,off);
return;
}
if (off >= get_way_size())
{
cout << "why the way size is overflow?" << endl;
return;
}
StationWayEntry t_station_way = station_table[from_id];
for (int i = t_station_way.size() - 1;i >= 0;i--)
{
int t_way = t_station_way[i];
if (b_way_visit[t_way] == 1)
{
continue;
}
else
{
b_way_visit[t_way] = 1;
cur_best_way[off] = t_way;
WayRoute t_stations = way_table[t_way];
for (int j = t_stations.size() - 1;j >= 0;j--)
{
int t_stat = t_stations[j];
if (b_station_visit[t_stat] == 1)
{
continue;
}
else
{
b_station_visit[t_stat] = 1;
dfs_best_way(t_stat,to_id,cur_best_way,off + 1);
b_station_visit[t_stat] = 0;
}
}
b_way_visit[t_way] = 0;
}
}
return;
}
/**
* 计算搜索到的路径的价格
* 使用动态规划，具体参考《算法导论》 p193 装配线问题
*/
int calc_price(BestWay& t_best_way,int off)
{
BestWay no_use_pre(off); /*当没有使用前一个时*/
BestWay use_pre(off); /*当使用前一个时*/
int temp_stat = t_best_way[0];
int temp_stat2 = 0;
use_pre[0] = no_use_pre[0] = price_table[temp_stat][0];
for (int i = 1;i < off;i++)
{
temp_stat = t_best_way[i];
no_use_pre[i] = min(no_use_pre[i - 1],use_pre[i - 1]) + price_table[temp_stat][0];
temp_stat2 = t_best_way[i - 1];
if (price_table[temp_stat2][temp_stat] != 0)
{
use_pre[i] = no_use_pre[i - 1] - price_table[temp_stat2][0] + price_table[temp_stat][temp_stat2];
}
else
{
use_pre[i] = no_use_pre[i - 1] + price_table[temp_stat][0];
}
}
return min(no_use_pre[off - 1],use_pre[off - 1]);
}
private:
typedef map<string,int> StationIdEntry;
typedef map<string,int> WayIdEntry;
/*由站名到id的映射*/
StationIdEntry station_id;
/*又路名到id的映射*/
WayIdEntry way_id;
/*这两个用来递增路和站的id*/
int way_size;
int station_size;
typedef map<int,string> WayNameEntry;
/*打印的时候要知道线路的名称，所以使用一个转换*/
WayNameEntry way_name;
typedef vector<int> WayRoute;
typedef vector<WayRoute> WayTable;
/*存所有线路及其经过的站id*/
WayTable way_table;
typedef vector<int> StationWayEntry;
typedef vector<StationWayEntry> StationWayTable;
/*存该站经过的所有线路id*/
StationWayTable station_table;
typedef vector<int> PriceInner;
typedef vector<PriceInner> PriceTable;
/*存所有的价格，全部以二维方式存储，当存在联票，则在对应二维空间填票价
*否则对应二维空间价格为0
*/
PriceTable price_table;
/*最后找到的最优路径，为线路id序列*/
BestWay best_way;
/*最优线路所需的价格*/
int best_price;
/*最优线路所经过站的个数*/
int best_way_size;
typedef vector<int> BoolVec;
/*这两个变量留给搜索时使用*/
BoolVec b_station_visit;
BoolVec b_way_visit;
};
int main()
{
SubWay sub_way;
std::fstream price_fstr("price.txt",ios_base::in);
std::fstream stations_fstr("stations.txt",ios_base::in);
sub_way.read_station(stations_fstr);
sub_way.read_price(price_fstr);
while (!cin.eof())
{
string station_name_from,station_name_to;
char ch = 0;
while(cin.get(ch) && ch != ',')
{
station_name_from += ch;
}
while(cin.get(ch) && ch != '\n')
{
station_name_to += ch;
}
sub_way.search_best_way(station_name_from,station_name_to);
}
return 0;
}
题四测试数据一：
price.txt
线1 180 线2 250 线4 160 线5 270 线8 175 线10 226 线13 114 线1,线2 350 线1,线10 390 线1,线5 410 线1,线4 330 线10,线13 310 线2,线5 390 线4,线10 370 线4,线13 260
station.txt
线1 苹果园 古城路 八角游乐园 八宝山 玉泉路 五棵松 万寿路 公主坟 军事博物馆 木樨地 南礼士路 复兴门 西单 天安门西 天安门东 王府井 东单 建国门 永安里 国贸 大望路 四惠 四惠东 线2 西直门 车公庄 阜成门 复兴门 长椿街 宣武门 和平门 前 门 崇文门 北京站 建国门 朝阳门 东四十条 东直门 雍和宫 安定门 鼓楼大街 积水潭 线4 公益西桥 角门西 马家堡 北京南站 陶然亭 菜市口 宣武门 西单 灵境胡同 西四 平安里 新街口 西直门 动物园 国家图书馆 魏公村 人民大学 海淀黄庄 中关村 北京大学东门 圆明园 西苑 北宫门 安河桥北 线5 天通苑北 天通苑 天通苑南 立水桥 立水桥南 北苑路北 大屯路东 惠新西街北口 惠新西街南口 和平西桥 和平里北街 雍和宫 北新桥 张自忠路 东四 灯市口 东单 崇文门 磁器口 天坛东门 蒲黄榆 刘家窑 宋家庄 线8 森林公园南门 奥林匹克公园 奥体中心 北土城 线10 巴沟 苏州街 海淀黄庄 知春里 知春路 西土城 牡丹园 健德门 北土城 安贞门 惠新西街南口 芍药居 太阳宫 三元桥 亮马桥 农业展览馆 团结湖 呼家楼 金台夕照 国贸 双井 劲松 线13 西直门 大钟寺 知春路 五道口 上地 西二旗 龙泽 回龙观 霍营 立水桥 北苑 望京西 芍药居 光熙门 柳芳 东直门
题四测试数据二：
price.txt
线1 180 线2 250 线4 160 线5 270 线8 175 线10 226 线13 114 线1,线2 350 线1,线10 390 线1,线5 410 线1,线4 330 线10,线13 310 线2,线5 390 线4,线10 370 线4,线13 260
station.txt
线1 苹果园 古城路 八角游乐园 八宝山 玉泉路 五棵松 万寿路 公主坟 军事博物馆 木樨地 南礼士路 复兴门 西单 天安门西 天安门东 王府井 东单 建国门 永安里 国贸 大望路 四惠 四惠东 线2 西直门 车公庄 阜成门 复兴门 长椿街 宣武门 和平门 前 门 崇文门 北京站 建国门 朝阳门 东四十条 东直门 雍和宫 安定门 鼓楼大街 积水潭 线4 公益西桥 角门西 马家堡 北京南站 陶然亭 菜市口 宣武门 西单 灵境胡同 西四 平安里 新街口 西直门 动物园 国家图书馆 魏公村 人民大学 海淀黄庄 中关村 北京大学东门 圆明园 西苑 北宫门 安河桥北 线5 天通苑北 天通苑 天通苑南 立水桥 立水桥南 北苑路北 大屯路东 惠新西街北口 惠新西街南口 和平西桥 和平里北街 雍和宫 北新桥 张自忠路 东四 灯市口 东单 崇文门 磁器口 天坛东门 蒲黄榆 刘家窑 宋家庄 线8 森林公园南门 奥林匹克公园 奥体中心 北土城 线10 巴沟 苏州街 海淀黄庄 知春里 知春路 西土城 牡丹园 健德门 北土城 安贞门 惠新西街南口 芍药居 太阳宫 三元桥 亮马桥 农业展览馆 团结湖 呼家楼 金台夕照 国贸 双井 劲松 线13 西直门 大钟寺 知春路 五道口 上地 西二旗 龙泽 回龙观 霍营 立水桥 北苑 望京西 芍药居 光熙门 柳芳 东直门
题四测试数据三：
price.txt
A 100 B 4 C 6 D 5 E 5 F 8 G 8 H 1 C,D 8 F,H 7
station.txt
A A1 AB AD B B1 AB BC BE C C1 BC DC CG D D1 AD CD DE E E1 BE DE EF F F1 EF FH G G1 CG GH H H1 GH FH
题四测试数据五：
price.txt
A 1 B 2 C 3 D 6 E 5 F 4 G 7 H 8 I 9 J 10 K 13 L 12 M 11 N 14 O 15 P 16 L,O 25
station.txt
A A1 AB AC B B1 AB BD BE C C1 AC CE D D1 BD DG DH E E1 BE EH CE EI F F1 CF FI FJ G G1 DG GK H H1 DH EH HK HL I I1 EI FI IL IM J J1 FJ JM K K1 GK HK KN L L1 HL IL LN LO M M1 IM JM MO N N1 KN LN NP O O1 LO MO OP P P1 NP OP
题五：
/**
BMP是常见的图像存储格式。
如果用来存黑白图像（颜色深度=1），则其信息比较容易读取。
与之相关的数据：
（以下偏移均是从文件头开始）
偏移：10字节, 长度4字节： 图像数据真正开始的位置。
偏移：18字节, 长度4字节： 位图的宽度，单位是像素。
偏移：22字节, 长度4字节： 位图的高度，单位是像素。
从图像数据开始处，每个像素用1个二进制位表示。
从图片的底行开始，一行一行向上存储。
Windows规定图像文件中一个扫描行所占的字节数必须是4字节的倍数，
不足的位均以 0 填充。例如，图片宽度为45像素，实际上每行会占用
8个字节。
可以通过Windows自带的画图工具生成和编辑二进制图像。
需要在“属性”中选择“黑白”，指定为二值图像。
可能需要通过 查看 | 缩放 | 自定义... 把图像变大比例一些，
更易于操作。
图像的左下角为图像数据的开始位置。白色对应1，黑色对应0
我们可以定义：两个点距离如果小于2个像素，则认为这两个点连通。
也就是说：以一个点为中心的九宫格中，围绕它的8个点与它都是连通的。
如：t1.bmp 所示，左下角的点组成一个连通的群体；
而右上角的点都是孤立的。
程序的目标是：根据给定的黑白位图，分析出所有独立连通的群体，
输出每个连通群体的面积。所谓面积，就是它含有的像素的个数。
输入数据固定存在in.bmp中。
如示例的in.bmp,
程序应该输出：
12
81
52
133
该输出表示：共有4个连通群体。
输出的连通体面积间的顺序可以随意。
请编程解决上述问题。
我们测试程序的时候，会使用不同的in.bmp文件。
要求考生把所有函数写在一个文件中。调试好后，存入与考生文件夹下对应题号的“解答.txt”中即可。
相关的工程文件不要拷入。
对于编程题目，要求选手给出的解答完全符合ANSI C标准，不能使用c++特性；
不能使用诸如绘图、中断调用等硬件相关或操作系统相关的API。
*/
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
using namespace std;
typedef vector<vector<int> > Bitmap;
static int width;
static int hight;
vector<int> head_counter;
struct HeadList
{
int prev;
int next;
};
vector<HeadList> headlist;
/*得到头部,若x，y点是白色的点*/
int get_head(Bitmap& bitmap,int x,int y)
{
if (x < 0 || y < 0 || x >= hight || y >= width)
{
return 0;
}
/*注意检查x y边界*/
int head = bitmap[x][y];
while (headlist[head].prev != 0)
{
head = headlist[head].prev;
}
return head;
}
void set_head(Bitmap& bitmap,int x,int y,int head)
{
bitmap[x][y] = head;
return;
}
/**
* 将第n项递增
*/
void increase(int n)
{
head_counter[n] += 1;
return;
}
/*将a b两个连接连起来*/
void link(int head_a,int head_b)
{
if (head_a == head_b)
{
return;
}
else if (head_a > head_b)
{
swap(head_b,head_a);
}
/*找到最后一个点，将其连接*/
while (headlist[head_a].next != 0)
{
head_a = headlist[head_a].next;
}
headlist[head_b].prev = head_a;
headlist[head_a].next = head_b;
return;
}
int new_head()
{
head_counter.push_back(0);
return head_counter.size() - 1;
}
void get_ans()
{
for (int i = 0;i < head_counter.size();i++)
{
if (headlist[i].next != 0 || headlist[i].prev != 0)
{
int res = 0;
int k = i,n = 0;
while (headlist[k].next != 0)
{
res += head_counter[k];
head_counter[k] = 0;
n = headlist[k].next;
headlist[k].prev = 0;
headlist[k].next = 0;
k = n;
}
res += head_counter[k];
head_counter[k] = 0;
headlist[k].prev = 0;
cout << res << endl;
}
else if (head_counter[i] != 0)
{
cout << head_counter[i] << endl;
head_counter[i] = 0;
}
}
return;
}
/**
* 递推版本
*/
void works(Bitmap& bitmap)
{
headlist.resize(hight * width / 4);
head_counter.push_back(0);
/*0位保留*/
int direct_x[4] = {0,-1,-1,-1};
int direct_y[4] = {-1,-1,0,1};
for (int i = 0;i < hight;i++)
{
for (int j = 0;j < width;j++)
{
/*是白色，继续*/
if (bitmap[i][j] == 0)
{
continue;
}
bitmap[i][j] = 0;
/*是黑色*/
for (int k = 0;k < 4;k++)
{
/*得到当前相邻点的头*/
int head = get_head(bitmap,i + direct_x[k],j + direct_y[k]);
if (head != 0)
{
/*已被上次标记*/
int head_2 = get_head(bitmap,i,j);
if (head_2 != 0)
{
/*这两个头结点连接起来*/
link(head_2,head);
}
else
{
increase(head);
set_head(bitmap,i,j,head);
}
}
}
int head = get_head(bitmap,i,j);
if (head == 0)
{
/*给当前点一个新的头*/
head = new_head();
increase(head);
set_head(bitmap,i,j,head);
}
}
}
return;
}
int main()
{
fstream fbmp("in.bmp",ios::in);
int start_pos;
fbmp.seekg(10,ios::beg);
fbmp.read((char*)&start_pos,sizeof(start_pos));
fbmp.seekg(18,ios::beg);
fbmp.read((char*)&width,sizeof(width));
fbmp.read((char*)&hight,sizeof(hight));
fbmp.seekg(start_pos,ios::beg);
Bitmap bitmap(hight);
int temp_width = (width / 32 + (width % 32 ? 1 : 0)) * 32;
for (int i = 0;i < hight;i++)
{
char ch;
int q = 0;
bitmap[i].resize(temp_width);
for (int j = 0;j < temp_width / 8;j++)
{
fbmp.get(ch);
for (int k = 0x80;k >= 0x01;k = (k >> 1) & 0xff)
{
if (ch & k)
{//白色
bitmap[i][q++] = 0;
}
else
{//黑色
bitmap[i][q++] = 1;
}
}
}
}
works(bitmap);
get_ans();
return 0;
}
题五深搜版本，此版本最后一个测试数据会出现栈溢出，使用广搜则不会
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
typedef vector<vector<int> > Bitmap;
static int width;
static int hight;
static int ans;
bool b_back = false;
void dfs(Bitmap& bitmap,int x,int y,bool flag)
{
if (x < 0 || y < 0 || x >= hight || y >= width || flag == 1 || bitmap[x][y] == 0)
{
return;
}
bitmap[x][y] = 0;
ans += 1;
for (int i = x - 1;i <= x + 1;i++)
{
for (int j = y - 1;j <= y + 1;j++)
{
dfs(bitmap,i,j,i == x && j == y);
}
}
return ;
}
int main()
{
fstream fbmp("t4.bmp",ios::in);
int start_pos;
fbmp.seekg(10,ios::beg);
fbmp.read((char*)&start_pos,sizeof(start_pos));
fbmp.seekg(18,ios::beg);
fbmp.read((char*)&width,sizeof(width));
fbmp.read((char*)&hight,sizeof(hight));
fbmp.seekg(start_pos,ios::beg);
Bitmap bitmap(hight);
int temp_width = (width / 32 + (width % 32 ? 1 : 0)) * 32;
for (int i = 0;i < hight;i++)
{
char ch;
int q = 0;
bitmap[i].resize(temp_width);
for (int j = 0;j < temp_width / 8;j++)
{
fbmp.get(ch);
for (int k = 0x80;k >= 0x01;k = (k >> 1) & 0xff)
{
if (ch & k)
{//白色
bitmap[i][q++] = 0;
}
else
{
bitmap[i][q++] = 1;
}
}
}
}
for (int i = 0;i < hight;i++)
{
for (int j = 0;j < width;j++)
{
if (bitmap[i][j] == 1)
{
ans = 0;
dfs(bitmap,i,j,0);
cout << ans << endl;
}
}
}
return 0;
}
题五广搜版本：
/**
* 广度优先搜索
*/
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
using namespace std;
typedef vector<vector<int> > Bitmap;
static int width;
static int hight;
static int ans;
bool b_back = false;
static int direct_x[8] = {-1,-1,-1,0,0,1,1,1};
static int direct_y[8] = {-1,0,1,-1,1,-1,0,1};
struct Point
{
int x,y;
Point(int t_x,int t_y)
:x(t_x),
y(t_y)
{
return;
}
};
void bfs(Bitmap& bitmap,int x,int y)
{
deque<Point> deq;
Point p(x,y);
bitmap[x][y] = 0;
deq.push_back(p);
ans += 1;
int x0 = 0,y0 = 0;
while (deq.empty() == false)
{
p = deq.front();
deq.pop_front();
for (int i = 0;i < 8;i++)
{
x0 = p.x + direct_x[i];
y0 = p.y + direct_y[i];
if (x0 < 0 || y0 < 0 || x0 >= hight || y0 >= width || bitmap[x0][y0] == 0)
{
continue;
}
else
{
bitmap[x0][y0] = 0;
ans += 1;
deq.push_back(Point(x0,y0));
}
}
}
return ;
}
int main()
{
fstream fbmp("t5.bmp",ios::in);
int start_pos;
fbmp.seekg(10,ios::beg);
fbmp.read((char*)&start_pos,sizeof(start_pos));
fbmp.seekg(18,ios::beg);
fbmp.read((char*)&width,sizeof(width));
fbmp.read((char*)&hight,sizeof(hight));
fbmp.seekg(start_pos,ios::beg);
Bitmap bitmap(hight);
int temp_width = (width / 32 + (width % 32 ? 1 : 0)) * 32;
for (int i = 0;i < hight;i++)
{
char ch;
int q = 0;
bitmap[i].resize(temp_width);
for (int j = 0;j < temp_width / 8;j++)
{
fbmp.get(ch);
for (int k = 0x80;k >= 0x01;k = (k >> 1) & 0xff)
{
if (ch & k)
{//白色
bitmap[i][q++] = 0;
}
else
{
bitmap[i][q++] = 1;
}
}
}
}
for (int i = 0;i < hight;i++)
{
for (int j = 0;j < width;j++)
{
if (bitmap[i][j] == 1)
{
ans = 0;
bfs(bitmap,i,j);
cout << ans << endl;
}
}
}
return 0;
}