Algorithm 版 (精华区)

发信人: xiaoying (xiaoying), 信区: Algorithm
标  题: 1103K-Hike on a Graph-ZJU
发信站: 哈工大紫丁香 (2002年10月09日17:19:30 星期三), 站内信件

#include "stdio.h"
#include "iostream.h"
#include "stdlib.h"
#include <iostream>
#include <vector>
using namespace std ;
int color[51][51];                            //颜色矩阵
int N;                                        // N*N
class status
{
public : status() {p1=p2=p3=-1;}
         //status & operator = (status &tmp)     { this->p1=tmp.p1; 
this->p2=tmp.p2;
 this->p3=tmp.p3; return *this;}
         int p1,p2,p3;
};
status Restore[10000];
int Rcount;
bool Isidentical(status a,status b)
{
   if(a.p1!=b.p1) return false;
   if(a.p2!=b.p2) return false;
   if(a.p3!=b.p3) return false;
   return true;
}
bool IsUsed(status a)
{
  for(int i=0;i<Rcount;i++)
      if(Isidentical(a,Restore[i]))
          return true;
  return false;
}
void SetUsed(status a)
{
 Restore[Rcount]=a;
 Rcount++;
}
void Search(vector<status> p,int n,int i)       //第i层  from 0 on , p 有n个
状态
{  // status *pp=new status[n*3*50];
    vector <status> pp;
    int count=0;
    status tmp;
//  for(int s=0;s<n;s++)
//  printf("%d %d %d \n",p[s].p1,p[s].p2,p[s].p3);
   for(int ii=1;ii<=N;ii++)
       {
       for(int jj=0;jj<n;jj++)
           {   if(p[jj].p1==p[jj].p2 && p[jj].p2==p[jj].p3) 
{printf("%d\n",i); pp.
clear(); return;}
               
if(color[p[jj].p1][ii]==color[p[jj].p2][p[jj].p3]&&p[jj].p1!=ii)    
               {tmp.p1=ii; tmp.p2=p[jj].p2; tmp.p3=p[jj].p3; 
if(!IsUsed(tmp))   { pp.
push_back(tmp); SetUsed(tmp); count++; } }
               
if(color[p[jj].p2][ii]==color[p[jj].p1][p[jj].p3]&&p[jj].p2!=ii)
               {tmp.p2=ii; tmp.p1=p[jj].p1; tmp.p3=p[jj].p3; 
if(!IsUsed(tmp))   {pp.p
ush_back(tmp); SetUsed(tmp); count++;} }
               
if(color[p[jj].p3][ii]==color[p[jj].p1][p[jj].p2]&&p[jj].p3!=ii)
               {tmp.p3=ii; tmp.p1=p[jj].p1; tmp.p2=p[jj].p2;  
if(!IsUsed(tmp)) {pp.pu
sh_back(tmp); SetUsed(tmp); count++;} }
           }
    
       }
   if(count==0) { printf("impossible\n"); return ;}
   Search(pp,count,i+1);
   pp.clear();
}
int main(int argc, char* argv[])
{
    int p1,p2,p3;
    
    char tmp[10];
//  freopen("E:\\in.txt","r",stdin);
    while(true)
    {
    Rcount=0;
    vector <status> begining;
    scanf("%d",&N);
    if(N==0) return 0;
    scanf("%d %d %d",&p1,&p2,&p3);         //p1,p2,p3的地方
    
    for(int i=1;i<=N;i++)
       for(int j=1;j<=N;j++)
       { scanf("%s",tmp); color[i][j]=tmp[0]; }        // 输入颜色矩阵
    status tmp;
    tmp.p1=p1;
    tmp.p2=p2;
    tmp.p3=p3;
    begining.push_back(tmp);
    Search(begining,1,0);
    begining.clear();
    }
    
    return 0;
}
 
--

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.226.228]