读书人

ACM 路径有关问题

发布时间: 2012-02-27 10:00:22 作者: rapoo

ACM 路径问题
题目是:
http://acm.nuaa.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1032

#include<iostream>
using namespace std;
int a[120][120];
bool DFS(int n,int begin,int end)
{
if(begin==end)
return true;
int i;
for(i=0;i<n;++i)
if(a[begin][i])
if(DFS(n,i,end))return true;
return false;
}
int main()
{
int n;int i,j,m;cin>>n;int begin,end;
for(i=0;i<n;++i)
for(j=0;j<n;++j)
{
cin>>a[i][j];
if(i==j)a[i][j]=0;
}
cin>>m;
for(i=0;i<m;++i)
{
cin>>begin>>end;

if(DFS(n,begin-1,end-1))cout<<"yes"<<endl;
else cout<<"no"<<endl;
}

return 0;
}

提交后显示:
Runtime Error at Test 2
(STACK_OVERFLOW)
为什么呢????

我想问个不该问的问题:在csdn上发代码时候,比如上面,怎样让它对对齐,就像在VC6.0编辑框里一样,我发现一把代码写到csdn发帖框里,关键字的字体也变了,代码缩进也变了?请教高手给指点一下,刚来csdn,不懂规矩,见谅了!



[解决办法]
我改进了一下,没用递归,怎么也是不正确,帮忙看一下
#include<iostream>
using namespace std;
int a[105][105];int flag[200]={0};
bool DFS(int n,int begin,int end)
{
int stack[200],top=0;
int i ;int w;int s=0;
stack[top++]=begin;flag[begin]=1;
while(top>0)
{
w=stack[--top];
for(i=0;i<n;++i)
if(a[w][i]&&flag[i]==0)
{
if(i==end){s=1;break;}
flag[i]=1;
stack[top++]=i;
}
}
if(s==1)return true;
else return false;
}
int main()
{
int n;int i,j;int m,begin,end;
while(cin>>n)
{
for(i=0;i<n;++i)
for(j=0;j<n;++j)
cin>>a[i][j];
cin>>m;
for(i=0;i<m;++i)
{cin>>begin>>end;
if(DFS(n,begin-1,end-1))
cout<<"yes"<<endl;
else
cout<<"no"<<endl;
}
}
return 0;
}

读书人网 >软件架构设计

热点推荐