2067137 2006-09-14 22:42:54 Accepted 2416 C++ 00:00.89 956K St.Crux     看来我要好好练习，bfs也可以编的很复杂。比如......1649的迷宫我已经WrongAnswer了十来遍了，每一遍都能激动地发现新的错误、作出愉快的改正，然后继续陷入郁闷。     这题还算基本的bfs，一遍ac的感觉真好。STL虽然占内存，也有他的好处。用上queue以后，我就不用再模拟队列了。 #include <iostream>#include <cstring>#include <string>#include <queue>using namespace std; int n, b[10000], pi, si;string s, p;queue <string> sq, tq; void init();int stoi(string);void bfs();void print(); int main(){ //freopen("in.txt", "r", stdin); cin >> n; int i; for(i = 0; i < n; i ++) {  cin >> s >> p;  init();  bfs();  print(); }  return 0;} void init(){ pi = stoi(p); si = stoi(s); memset(b, 0, sizeof(b)); b[si] = 1; sq = tq; sq.push(s);} int stoi(string str){ int sum = 0, i; for(i = 0; i < 4; i ++) {  sum *= 10;  sum += str[i] - '0'; } return sum;} void bfs(){ string ts, ss; int ti, ii, l, i; while(!sq.empty()) {  ts = sq.front();  ti = stoi(ts);  l = b[ti];  if(ti == pi) break;  for(i = 0; i < 3; i ++)  {   ss = ts;   char tc = ss[i];   ss[i] = ss[i + 1];   ss[i + 1] = tc;   ii = stoi(ss);   if(!b[ii])   {    b[ii] = l + 1;    sq.push(ss);   }  }  for(i = 0; i < 4; i ++)  {   ss = ts;   ss[i] = (ss[i] != '9') ? ss[i] + 1 : '1';   ii = stoi(ss);   if(!b[ii])   {    b[ii] = l + 1;    sq.push(ss);   }   ss = ts;   ss[i] = (ss[i] != '1') ? ss[i] - 1 : '9';   ii = stoi(ss);   if(!b[ii])   {    b[ii] = l + 1;    sq.push(ss);   }  }  sq.pop(); }} void print(){ printf("%d\n", b[pi] - 1);}    

评论