首页 > 代码库 > sicily 1150,1151
sicily 1150,1151
// Problem#: 1151 // Submission#: 2982372 // The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License // URI: http://creativecommons.org/licenses/by-nc-sa/3.0/ // All Copyright reserved by Informatic Lab of Sun Yat-sen University #include<iostream> #include<queue> #include<stdio.h> using namespace std; struct node { int a; int b; string path; int sum; node() { sum = 0; } }; struct hash { int n; hash *next; }; node end; queue<node> q; int n; bool sign; hash *ju[10000]; bool cmp(node temp) { if(temp.a == end.a && temp.b == end.b){ sign = 1; return true; } else { return false; } } bool judge(node temp) { if(ju[temp.a] == NULL) { ju[temp.a] = new hash(); (ju[temp.a])->n = temp.b; (ju[temp.a])->next = NULL; return true; } else { hash *p; p = ju[temp.a]; if(p->n == temp.b) { return false; } else { while(p->next != NULL) { p = p->next; if(p->n == temp.b) { return false; } } p->next= new hash(); p = p->next; p->n = temp.b; p->next = NULL; return true; } } } void Achange(node temp) { if(sign == 0 && temp.sum < n) { int a1; a1 = temp.a; temp.a = temp.b; temp.b = a1; (temp.path).push_back(‘A‘); temp.sum++; if(cmp(temp)) { end.path = temp.path; end.sum = temp.sum; } else { if(judge(temp)) { q.push(temp); } } } } void Bchange(node temp) { if(sign == 0 && temp.sum < n) { int a1; int b1; a1 = temp.a % 10; b1 = temp.b % 10; temp.a = temp.a/10 + a1*1000; temp.b = temp.b/10 + b1*1000; (temp.path).push_back(‘B‘); temp.sum++; if(cmp(temp)) { end.path = temp.path; end.sum = temp.sum; } else { if(judge(temp)) { q.push(temp); } } } } void Cchange(node temp) { if(sign == 0 && temp.sum < n) { int g1,s1,b1,q1,g2,s2,b2,q2; g1 = temp.a%10; s1 = (temp.a%100)/10; b1 = (temp.a%1000)/100; q1 = temp.a/1000; g2 = temp.b%10; s2 = (temp.b%100)/10; b2 = (temp.b%1000)/100; q2 = temp.b/1000; temp.a = q1*1000 + b2*100 + b1*10 +g1; temp.b = q2*1000 + s2*100 + s1*10 + g2; (temp.path).push_back(‘C‘); temp.sum++; if(cmp(temp)) { end.path = temp.path; end.sum = temp.sum; } else { if(judge(temp)) { q.push(temp); } } } } int main() { while(cin>>n && n != -1) { for(int i = 0; i < 10000; i++) { ju[i] = NULL; } int a = 0; int b = 0; char c; c=getchar(); c=getchar(); while(c != ‘\n‘) { if(c != ‘ ‘) { a = a*10 + (int)(c - ‘0‘); } c = getchar(); } c = getchar(); while(c != ‘\n‘) { if(c != ‘ ‘) { b = b*10 + (int)(c - ‘0‘); } c = getchar(); } node start; start.sum = 0; start.a = 1234; start.b = 8765; end.a = a; end.b = b; end.sum = 0; end.path = ""; q.push(start); sign = 0; ju[1234] = new hash(); (ju[1234])->n = 8765; (ju[1234])->next = NULL; if(cmp(start)) { } while(!q.empty() && sign == 0) { Achange(q.front()); Bchange(q.front()); Cchange(q.front()); q.pop(); } if(sign == 1) { cout << end.sum << " " << end.path << endl; } else { cout << "-1" <<endl; } } }
sicily 1150,1151
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。