巢穴

about:blank

P1753

  -_-||| 
  一直runtime error
   然后再poj上找到了数据
   测试数据正确
   于是怀疑是我用<map>的问题,疑惑不解中
#include <iostream>
#include <string>
#include <map>
#include <queue>
using namespace std;

queue<string> list; 
queue<int> list_t;
map<string,int> hash;

void init()
{
     
     string str="";
     for (int i=0;i<4;i++)
     {
         for (int j=0;j<4;j++)
         {
             char ch;
             cin>>ch;
             //ch=getchar();
             str+=ch;
         }
         getchar();
     }

     if (str=="bbbbbbbbbbbbbbbb"||str=="wwwwwwwwwwwwwwww")
     {
            cout<<0<<endl;
            exit(0);
     } 
     list.push(str);
     list_t.push(0);
     hash.insert(map<string,int>::value_type(str,0));
}
void turn(char &ch)
{
     if (ch=='w') ch='b';
     else ch='w';
}
void bfs()
{
     while (!list.empty())
     {
      string str=list.front();

      int ti=list_t.front();
      list.pop();
      list_t.pop();
      for (int i=0;i<16;i++)
      {
          string s=str;

          int x;
          //up
          turn(s[i]);
          x=i-4;
          if (i>=0) turn(s[x]);
          //down
          x=i+4;
          if (i<16) turn(s[x]);
          //left
          if (i%4!=0) {x=i-1;turn(s[x]);}
          //right
          if (i%4!=3) {x=i+1;turn(s[x]);}
          
          map<string,int>::iterator iter=hash.find(s);
          if (iter==hash.end())
          {
           list.push(s);
           list_t.push(ti+1);


           if (s=="bbbbbbbbbbbbbbbb"||s=="wwwwwwwwwwwwwwww")
           {
            cout<<ti+1<<endl;
            exit(0);
            
           } 
           hash.insert(map<string,int>::value_type(s,ti+1));
          }
        
      }
     }
     cout<<"Impossible"<<endl;
}

int main()
{
    init();
    bfs();
    return 0;
}

posted on 2009-10-01 14:32 Vincent 阅读(236) 评论(0)  编辑 收藏 引用 所属分类: 数据结构与算法


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理