看来我要好好练习，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);
}

评论