巢穴

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   知识库   博问   管理