|
20鱼币
这是题目传送门:
http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1004
我的代码是:
- #include <iostream>
- using namespace std;
- bool DFS(bool station[150][150],int posx,int posy,int end,bool column[101],int max);
- int main()
- {
- int T; //0<T<30
- int start,end; //[0,100]
- int n; //0<n<=50
- cin>>T;
- for (int i=0;i<T;i++)
- {
- int max=-1;
- bool station[150][150]={{false}}; //邻接矩阵
- bool column[150]={false}; //记录某列是否已经走过
- cin>>start>>end>>n;
- int temp,before;
- while (1)
- {
- if ('\n' == cin.peek())
- {
- before=-1;
- if (0 == n--) break;
- }
- cin>>temp;
- if (temp > max) max=temp;
- if (-1 == before) before=temp;
- else if (temp == before) continue;
- else station[temp][before]=station[before][temp]=true;
- }
- if (DFS(station,start,0,end,column,max)) cout<<"Yes"<<endl;
- else cout<<"No"<<endl;
- }
- return 0;
- }
- bool DFS(bool station[150][150],int posx,int posy,int end,bool column[101],int max)
- {
- if (posy == end && true == station[posx][end])
- return true;
- else if (posy > max)
- return false;
- if (true == station[posx][posy] && false == column[posy])
- {
- column[posy]=true;
- if (DFS(station,posy,0,end,column,max)) return true;
- column[posy]=false;
- }
- return DFS(station,posx,posy+1,end,column,max);
- }
复制代码 系统说我执行时间超过了1s,是不是DFS在此不适用?:mad:
|
|