首页 > 代码库 > POJ3984 迷宫问题【水BFS】
POJ3984 迷宫问题【水BFS】
#include <cstdio> #include <cmath> #include <iostream> #include <algorithm> #include <cstdlib> #include <cstring> #include <map> #include <vector> using namespace std; map<string,int>mymap; map<string,int>::iterator it; #define LEN 1111 bool visited[LEN]; //bool arc[LEN][LEN]; vector<int> arc[555555]; int degree[LEN]; int n,m; bool is_v_i(int v,int i) { vector<int>::iterator it=find(arc[v].begin(),arc[v].end(),i); // for(it=arc[v].begin();it!=arc[v].end();i++) // { // if(it) // } if(it==arc[v].end()) return false; else return true; } void dfs(int v) //深度优先遍历 { visited[v]=true; for(int i=1;i<=n;i++) { if(!visited[i] && is_v_i(v,i)) { dfs(i); } } } bool isConnected() //查看遍历后结果 { for(int i=1;i<=n;i++) { if(!visited[i]){return false;} } return true; } bool isCircuit() //通过度数是否为偶数判断欧拉回路 { int oddnum=0; for(int i=1;i<=n;i++) { if(degree[i]%2) { oddnum++; if(oddnum>2) return false; } } return true; } int main() { #ifndef ONLINE_JUDGE freopen("D:/1.txt","r",stdin); //freopen("D:/2.txt","w",stdout); #endif int que=1; string s1,s2; while(cin>>s1>>s2) { int p,q; it=mymap.find(s1); if(it==mymap.end()) { mymap[s1]=que++; p=que-1; } else { p=it->second; } it=mymap.find(s2); if(it==mymap.end()) { mymap[s2]=que++; q=que-1; } else { q=it->second; } degree[p]++;degree[q]++;//没方向的 //arc[p][q]=arc[q][p]=true;//arc[p][q] ,p,q是否连通 arc[p].push_back(q); arc[q].push_back(p); } n=que-1; dfs(1); if(!isConnected()) { cout<<"Impossible"<<'\n'; } else{ if(isCircuit()) cout<<"Possible"<<'\n'; else cout<<"Impossible"<<'\n'; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。