/********************************
Written&by&:&phinecos(洞庭散人)
Data&&&&&&&:&2/11/
Description:&非递归，模拟系统堆栈解决类似八皇后问题
State&:&Accepted
Run&Time:&0ms
Run&Memory:&&&&184KB
****************************************/
#include&iostream&
#include&&stack&
using&namespace&
const&int&MAXSIZE&=&4;//&地图最大大小
char&map[MAXSIZE][MAXSIZE];//&地图
int&maxNum,n;
struct&Node
&&&&int&//行
&&&&int&//列
&&&&int&//当前层次
bool&CanPut(int&row,&int&col)
{//测试是否可以放置碉堡到row行col列处，因为位置是从小到大前进的，因此只需要测试比待测试点小的位置
&&&&int&i;
&&&&//测试col列上是否有面对面的碉堡
&&&&for&(i&=&row&-&1;&i&&=&0;&--i)
&&&&&&&&if&(map[i][col]&==&'O')&return&false;
&&&&&&&&if&(map[i][col]&==&'X')&break;
&&&&//测试row行上是否有面对面的碉堡
&&&&for&(i&=&col&-&1;&i&&=&0;&--i)
&&&&&&&&if&(map[row][i]&==&'O')&return&false;
&&&&&&&&if&(map[row][i]&==&'X')&break;
&&&&return&true;
void&Solve(int&k,int&curNum)
&&&&stack&Node&&s1;//解决树堆栈
&&&&int&row,col,i;
&&&&int&curLevel&=&0;//当前层次
&&&&//起始结点入栈
&&&&node.row=k/n;
&&&&node.col&=&k%n;
&&&&node.level&=&curL//当前堆栈层次是第0层
&&&&s1.push(node);
&&&&while&(!s1.empty())
&&&&&&&&node&=&s1.top();
&&&&&&&&row&=&node.
&&&&&&&&col&=&node.
&&&&&&&&&&&&
&&&&&&&&if&(map[row][col]=='.'&&CanPut(row,col)==true)
&&&&&&&&{//map[row][col]空闲并且经测试可以放置,则占据此位置
&&&&&&&&&&&&map[row][col]&=&'O';
&&&&&&&&&&&&//堆栈层次加1
&&&&&&&&&&&&curLevel++;
&&&&&&&&&&&&node.level&=&curL//作为这个堆栈层此的排头兵
&&&&&&&&&&&&s1.pop();
&&&&&&&&&&&&s1.push(node);
&&&&&&&&&&&&curNum++;//放置的棋子数目加1
&&&&&&&&if&(row==n-1&&col==n-1)
&&&&&&&&{//来到这个堆栈层的最后一个结点了
&&&&&&&&&&&&if&(curNum&maxNum)
&&&&&&&&&&&&{//保存这一层的最大数目
&&&&&&&&&&&&&&&&maxNum&=&curN
&&&&&&&&&&&&}
&&&&&&&&&&&&if&(curLevel==0)
&&&&&&&&&&&&{//若回到第0层，则说明已经考虑完所有情况了
&&&&&&&&&&&&&&&&break;
&&&&&&&&&&&&}
&&&&&&&&&&&&/*
&&&&&&&&&&&&*下面这段代码非常低级趣味，我居然用了两重while循环，It's rubbish,不喜勿进!!!!
&&&&&&&&&&&&*/
&&&&&&&&&&&&//去掉当前堆栈层
&&&&&&&&&&&&while&(!s1.empty())
&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&node&=&s1.top();
&&&&&&&&&&&&&&&&if&(node.level==curLevel)
&&&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&&&&&s1.pop();
&&&&&&&&&&&&&&&&&&&&--k;
&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&&&&&else
&&&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&&&&&curLevel--;
&&&&&&&&&&&&&&&&&&&&curNum--;
&&&&&&&&&&&&&&&&&&&&break;
&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&}
&&&&&&&&&&&&//有一种情况是栈此时是空的，但还是需要将层次数和棋子数减1，因为循环中它给跳过去了。。。汗。
&&&&&&&&&&&&if(s1.empty())
&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&curLevel--;
&&&&&&&&&&&&&&&&curNum--;
&&&&&&&&&&&&}
&&&&&&&&&&&&//将上一层的排头兵恢复回来（就是把'O'再此变回'.',并且层次改为这一层）
&&&&&&&&&&&&++k;
&&&&&&&&&&&&row&=&k/n;
&&&&&&&&&&&&col&=&k%n;
&&&&&&&&&&&&map[row][col]&=&'.';
&&&&&&&&&&&&node.row&=&
&&&&&&&&&&&&node.col&=&
&&&&&&&&&&&&node.level&=&curL
&&&&&&&&&&&&s1.push(node);
&&&&&&&&&&&&//以上一层排头兵的下一个结点为起点，继续
&&&&&&&&&&&&if&(k+1&n*n)
&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&++k;
&&&&&&&&&&&&&&&&node.row&=&k/n;
&&&&&&&&&&&&&&&&node.col&=&k%n;
&&&&&&&&&&&&&&&&node.level&=&curL
&&&&&&&&&&&&&&&&s1.push(node);
&&&&&&&&&&&&}
&&&&&&&&&&&&else
&&&&&&&&&&&&{//当来到最后一个元素时，又有一个特殊的情形，此时当前层次所有情况都已经考虑完毕，因此需要将当前堆栈层给清空掉，哎，这个清空动作和前面是一样的，可居然又单独列了遍代码，吐了。。。
&&&&&&&&&&&&&&&&if&(curLevel==0)
&&&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&&&&&break;
&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&&&&&while&(!s1.empty())
&&&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&&&&&node&=&s1.top();
&&&&&&&&&&&&&&&&&&&&if&(node.level==curLevel)
&&&&&&&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&&&&&&&&&s1.pop();
&&&&&&&&&&&&&&&&&&&&&&&&--k;
&&&&&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&&&&&&&&&else
&&&&&&&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&&&&&&&&&curLevel--;
&&&&&&&&&&&&&&&&&&&&&&&&curNum--;
&&&&&&&&&&&&&&&&&&&&&&&&break;
&&&&&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&&&&&if&(s1.empty())
&&&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&&&&&curLevel--;
&&&&&&&&&&&&&&&&&&&&curNum--;
&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&&&&&++k;
&&&&&&&&&&&&&&&&row&=&k/n;
&&&&&&&&&&&&&&&&col&=&k%n;
&&&&&&&&&&&&&&&&map[row][col]&=&'.';
&&&&&&&&&&&&&&&&node.row&=&
&&&&&&&&&&&&&&&&node.col&=&
&&&&&&&&&&&&&&&&node.level&=&curL
&&&&&&&&&&&&&&&&s1.push(node);
&&&&&&&&&&&&&&&&++k;
&&&&&&&&&&&&&&&&node.row&=&k/n;
&&&&&&&&&&&&&&&&node.col&=&k%n;
&&&&&&&&&&&&&&&&node.level&=&curL
&&&&&&&&&&&&&&&&s1.push(node);
&&&&&&&&&&&&}
&&&&&&&&&&&&
&&&&&&&&else
&&&&&&&&{//还没来到这一堆栈层次的最后一个节点，继续吧
&&&&&&&&&&&&++k;
&&&&&&&&&&&&node.row&=&k/n;
&&&&&&&&&&&&node.col&=&k%n;
&&&&&&&&&&&&node.level&=&curL
&&&&&&&&&&&&s1.push(node);
int&main()
&&&&int&i,j;
&&&&while(cin&&n&&n!=0)
&&&&&&&&//输入地图
&&&&&&&&for(i=0;i&n;i++)
&&&&&&&&&&&&for(j=0;j&n;j++)
&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&cin&&map[i][j];
&&&&&&&&&&&&}
&&&&&&&&maxNum=0;//最多可能放置的数目
&&&&&&&&//开始深搜,起点设置为左上角
&&&&&&&&Solve(0,0);
&&&&&&&&cout&&maxNum&&
&&&&return&0;
随笔 - 607
评论 - 1565
引用 - 117最短路径问题――这道题绝对经典(华为2014年校招机试题)
高级题：地铁换乘
已知2条地铁线路，其中A为环线，B为东西向线路，线路都是双向的。经过的站点名分别如下，两条线交叉的换乘点用T1、T2表示。编写程序，任意输入两个站点名称，输出乘坐地铁最少需要经过的车站数量（含输入的起点和终点，换乘站点只计算一次）。
地铁线A（环线）经过车站：A1??A2??A3??A4??A5??A6??A7??A8??A9??T1??A10??A11??A12??A13??T2??A14??A15??A16??A17??A18
地铁线A（直线）经过车站：B1??B2??B3??B4??B5??T1??B6??B7??B8??B9??B10??T2??B11??B12??B13??B14??B15
输入：输入两个不同的站名
输出：输出最少经过的站数,含输入的起点和终点，换乘站点只计算一次
思路解析：
我不知道大家看到这道题是怎么思考的，我看到这道题第一反映就是他要我求最短路径，而最短路径几种常用的算法是Dijkstra,Floyd和A*算法，而A*算法尤为常用（我对A*算法比较熟悉，之前做过这个项目），所以我不佳思索的就是开始用A*算法写了。先开始通过名字构建图....因为说实话这个图没有什么规律，必须一点点构建，特别是节点出的连接，构建图我大概花了20分钟，然后开始写A*算法。A*算法一个最关键的问题就是求代价值，而实际上这个问题并不好求代价值，但也不是不能求。我花了30分钟设计出代价值的函数，于是我开始反思，我觉得这样下去，加上我把A*算法重头写一遍，加上 调试应该还要1个小时左右的时间。可是华为这道题给我们的总共时间只有一个小时，于是我开始否认我的这一条思路了。
然后我又很自然的想到了，对于这种题用图的深度遍历，他将会得出多条路径，然后我可以选取最短的一条。这貌似是一个不错的方法，可是这样做的前提是我必须还要构建一个图出来，这样下来构建图依旧要花费20分钟，只有40分感觉时间比较紧张，可能对与容错处理和健壮性仍旧会考虑不佳。我又开始否认我这条思路。
我想，到底有没有一种编码效率更高的方法可以在最短时间内完成这个代码呢？我再次仔细读题，他只需要我输出最少经过的站数，并不对每一个站是哪个站做了要求，所以一个很笨但是却思维清晰的方法浮现在我脑海中。
分析可知：
这个图就出现了。我们可以把所有的线路分成五段和两个点，总共七中情况。所以如果我穷举所有的情况也就是7*7=49种，单实际上有很多情况我们只要把起点和终点交换一下就可以作为另一种情况了。接下来下面的代码就出现了
用时：总49分钟。起始只要思路清晰一种一种情况的写是不容易出错的，虽然这个代码维护起来比较麻烦。
#include &math.h&
判断这个名字在哪段路上
int Which(string name)
if(name[0] == 'B')//假设name1为起点，现在只考虑起点
if(atoi(&name[1]) &=5 && atoi(&name[1]) &= 1)
{//B为第一个路段
else if(atoi(&name[1]) &=10 && atoi(&name[1]) &= 6)
else if(atoi(&name[1]) &=15 && atoi(&name[1]) &= 11)
else if(name[0] == 'A')
if(atoi(&name[1]) &=13 && atoi(&name[1]) &= 10)
else if((atoi(&name[1]) &=9 && atoi(&name[1]) &= 1) || (atoi(&name[1]) &=15 && atoi(&name[1]) &= 11))
else if(name[0] == 'T')
if(atoi(&name[1]) == 1)
else if(atoi(&name[1]) &=13)
return 0;//不在这个路上的站点
#define T1_1(id) (6-id)
//1-&T1的站数
#define T2_1(id) (T1_1(id)+5)
//1-&T2的站数
#define T1_2(id) (id-8)
#define T2_2(id) (15-id)
#define T1_3(id) (id-4)
#define T2_3(id) (12-id)
#define T1_5(id) (6+id-10)
#define T2_5(id) (id-9)
//接口函数
int BestRouting(string name1,string name2)
//分为5段和两个节点考虑
//A1-A9+A14-A18
//1-&(2,5,3,4)的路径很容易分析
int id1 = atoi(&name1[1]),id2 = atoi(&name2[1]) ;
if(Which(name1) == 1)//起点在1路段上
if(Which(name2) == 1)//都在1路段
return abs(id1 - id2)+1;
else if(Which(name2) == 2)//结束路段在2
return T1_1(id1)+id2-9;
else if(Which(name2) == 3)//借宿路段在3
return T1_1(id1)+id2-5;
else if(Which(name2) == 4)
if(id2 & 17)
return T2_1(id1)+id2-13;
else if(id2 == 18)
return T1_1(id1)+11;
return T1_1(id1)+10-id2;
else if(Which(name2) == 5)
return T2_1(id1)+id2-10;
else if(Which(name2) == 6)
return T1_1(id1);
else if(Which(name2) == 7)
return T2_1(id1);
else if(Which(name1) == 2)
if(Which(name2) == 1)
return BestRouting(name2,name1);
else if(Which(name2) == 2)
return abs(id1-id2)+1;
else if(Which(name2) == 3)
if(id1 &= 11 && id2 &= 8)
return T1_2(id1)+T1_3(id2)-1;
if(id1 &= 12 && id2 & 8)
return T2_2(id1)+T2_3(id2)-1;
if(id1 &= 11 && id2 & 8)
return T2_2(id1)+T2_3(id2)-1;
return T1_2(id1)+T1_3(id2)-1;
else if(Which(name2) == 4)
if(id2 &= 3 && id2 &= 9)
return T1_2(id1)+10-id2;
else if(id2 & 3)
return T2_2(id1)+id2-1+6;
return T2_2(id1)+id2-13;
else if(Which(name2) == 5)
return T2_2(id1)+id2-10;
else if(Which(name2) == 6)
return T1_2(id1);
else if(Which(name2) == 7)
return T2_2(id1);
else if(Which(name1) == 3)
if(Which(name2) == 1)
return BestRouting(name2,name1);
else if(Which(name2) == 2)
return BestRouting(name2,name1);
else if(Which(name2) == 3)
return abs(id1-id2)+1;
else if(Which(name2) == 4)
if(id2 &= 3 && id2 &= 9)
return T1_3(id1)+10-id2;
else if(id2 & 3)
return T2_3(id1)+id2-1+6;
return T2_3(id1)+id2-13;
else if(Which(name2) == 5)
return id2-id1+2;
else if(Which(name2) == 6)
return T1_3(id1);
else if(Which(name2) == 7)
return T2_3(id1);
else if(Which(name1) == 4)
if(Which(name2) == 5)
if(id2 & 5 && id2 & 14)
return 15-id1+id2-10;
else if(id2 &= 5)
return id1+7+T2_5(id2);
return id1-13+T2_5(id2);
else if(Which(name2) == 6)
if(id1 &= 18 && id1 &= 14)
return 6+id1-13;
else if(id1 &= 9)
return 11-id2;
return 19-id1+10;
else if(Which(name2) == 7)
if(id1 &= 5 && id1 &= 9)
return 6+id1-8;
else if(id1 & 5)
return id1+6;
return id1 - 12;
else if(Which(name2) == 4)
if((id1 &= 9 && id1 &= 8) && (id2 &= 15 && id2 &= 14))
return 6+10-id1+id2-13;
if(id1 &= 9 && id2 &= 9)
return abs(id1-id2) + 1;
else if(id1 &= 14 && id2 &= 14)
return abs(id1-id2) + 1;
else if(id1&id2)
return 18-id1+id2+1;
else if(id1 & id2)
return 18-id2+id1+1;
else if(id1 == id2)
else if(Which(name2) != 0)
return BestRouting(name2,name1);
else if(Which(name1) == 5)
if(Which(name2) == 6)
return T1_5(id1);
else if(Which(name2) == 7)
return T2_5(id1);
else if(Which(name2) != 0)
return BestRouting(name2,name1);
else if(Which(name1) == 6)
if(Which(name2) == 6)
else if(Which(name2) == 7)
else if(Which(name2) != 0)
return BestRouting(name2,name1);
else if(Which(name1) == 7)
if(Which(name2) == 7
if(Which(name2) != 0)
return BestRouting(name2,name1);
return -1;
int main(int argc, char* argv[])
cout&&BestRouting(&A1&,&A11&);
这件事给我的感触挺深的，我想起我曾经一个老师怎么教我们的。她说过，永远没有最好的代码与最差的代码，永远是适合最好。我相信很多人绝对会觉得这个代码就是一个刚学几条语法的新手编出来的，但是这种新手代码在华为的考场上绝对能帮到你很大的忙。
当然，这个方法对于这种结构简单情况讨论清晰的题来是很好的，但是对于复杂的结构肯定就不能用这种方法了。
如果大家有更好的方法，希望大神教教我，谢谢。
您对本文章有什么意见或着疑问吗？请到您的关注和建议是我们前行的参考和动力&&
您的浏览器不支持嵌入式框架，或者当前配置为不显示嵌入式框架。zoj 1221这道题_百度知道
zoj 1221这道题
我用的是Dijsktra，一直WA，找不到哪错了#include &iostream&#include &vector&#define INF 100000vector&int& point[100];int dist[100];bool s[100];void Dijsktra(int u){ for(int i = 0;i &= 19;i++) {
dist[i] = INF; } for(int i = 0;i & point[u].size();i++) dist[point[u][i]] = 1;
s[u] = 1; dist[u] = 0; for(int i = 0;i &= 19;i++) {
int min = INF;
for(int j = 0;j &= 19;j++)
if(dist[j] & min && !s[j])
{min = dist[j];mark =}
s[mark] = 1;
for(int k = 0;k & point[mark].size();k++)
if(!s[ point[mark][k] ] && dist[ point[mark][k] ] & dist[mark] + 1 )
{dist[ point[mark][k] ] = dist[mark] + 1;}
}}int main(){
int count = 1;
憨敞封缎莩等凤劝脯滑
while(cin && n)
for(int j = 0;j &j++)
point[0].push_back(e);
point[e].push_back(0);
for(int i = 2;i &= 19;i++)
for(int j = 0;j &j++)
point[i - 1].push_back(e);
point[e].push_back(i - 1);
cout && &Test Set#& && count &&
for(int i = 0;i &i++)
cin && u &&
Dijsktra(u - 1);
cout && u && & to & && v && &: & && dist[v - 1] &&
for(int i = 0;i &= 19;i++)
point[i].clear();
//system(&pause&);
return 0;}
提问者采纳
我把你的程序编译了一下，编译环境是VS 2005，得到两个一样的warning:warning C4018: '&' : signed/unsigned mismatch憨敞封缎莩等凤劝脯滑指向的是这两行：for(int&i&=&0;i&&&point[u].size();i++)for(int&k&=&0;k&&&point[mark].size();k++)意思就是i和k是带符号的整型而size()返回的是不带符号的，这样的两个值之间作比较可能会有潜在风险
提问者评价
其他类似问题
zoj的相关知识
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁zoj上1002题 测试感觉没问题 提交报错_百度知道
zoj上1002题 测试感觉没问题 提交报错
b=1,0);=t,s+1,h+1,&str[i]);=t)r=run(
for(a=s+1;a&lt,b;=t)r=run(%d&quot.'
for(.h&gt,0,t-1;int run(char str[5][5],r),int t,s;=t;X'
for(a=h+1,t;
h=a,0.'}int main(){
char str[5][5];;t,r);a&lt,){
str[s][h]=&#39,,int r){a++){
if(str[a][h]=='%s&X&#39,&t);n&
str[s][a]='
if(b==1)r += b.'
if(str[s][h]==';i++){
scanf(&%d\,t;
printf(&;;X';,r);
int i,0;){
str[a][h]='
else if(s+1&;,t;i&
for(i=0,q贴代码#include&lt,r;a++){
if(str[s][a]=='#include&lt.h&){
scanf(&quot
我不要你们的程序 我只想知道我自己哪里错了
提问者采纳
第二维表示字符串中具体的字符, &str[i])，第一维表示字符串的地址;%s&quot，当然错了。在二维字符数组中;;%s&，&str[i]是求指针的地址即“char **”;”str[i]本省是个指针;”这句话出错了, str[i])，应改为“scanf(&quot“scanf(&quot
提问者评价
其他类似问题
按默认排序
其他1条回答
//&你的算法有点像贪心，能放一个就放一个//&这里应该用dfs进行搜索
zoj的相关知识
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁