Algorithm 版 (精华区)

发信人: Lerry (life is waiting...), 信区: Algorithm
标  题: 1008K-GnomeTetravex-ZJU
发信站: 哈工大紫丁香 (2002年10月14日19:52:25 星期一), 站内信件

不剪枝，直接搜

#include "iostream.h"
#include "stdio.h"
int times=0,n,possible,map[5][5],total,data[25][2],l[10],t[10];
const int status=0,amount=1,X=1,Y=0;
bool test(int col,int row,int p) 
{
    if(row>0){int y=map[row-1][col];if((p/1000)!=((y%100)/10)) return false;} 
    if(col>0){int y=map[row][col-1];if((p%10)!=((y%1000)/100)) return false;} 
    return true; 
} 
bool put(int p)
{
    if(p==n*n) return true;
    int xx=p%n;
    int yy=p/n;
    for(int i=0;i<total;i++)
        if(data[i][amount]>0)
            if(test(xx,yy,data[i][status]))
            {
                    map[yy][xx]=data[i][status];
                    data[i][amount]--;
                    if(put(p+1)) return true;
                    data[i][amount]++;
            }
            return false;
}
int main(int argc, char* argv[])
{
    int i,j,round,result,found;
#ifndef ONLINE_JUDGE
    freopen("gnome.in","r",stdin);
#endif
    cin>>n;
    while(true)
    {
        if(n==0)break;
        if(times!=0) cout<<endl;
        for(total=i=0;i<n*n;i++)
        {
            for(result=j=0;j<4;j++){cin>>round;result=result*10+round;}
            for(j=0;j<total;j++)
                if(data[j][0]==result){data[j][amount]++;break;}
            if(j==total){data[j][status]=result;data[j][amount]=1;total++;}
        }
        cout << "Game " << ++times << ": "; 
        if (put(0))     cout << "Possible" << endl; 
        else        cout << "Impossible" << endl; 
        cin>>n;     
    }
    return 0;
}
--
猜谜语：太监以前有，进宫后没有；
和尚有但是不用，外国人比中国人的长。
打一人身上的东西？想歪了吧——是名字！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.249.235]
※ 修改:·Lerry 於 10月14日19:54:08 修改本文·[FROM: 202.118.249.235]