2009年1月13日星期二

Shity Recursion

This is a program that could be used to calculate rook polynomial which is putting rooks in a irregular chess board( more specifically, it can partially solve sgu269). Almost killed by recursion.
#include <iostream>
#include <fstream>
#include <memory>
using namespace std;
fstream fin;
int n,k,num[5],rk[5],ans[5][8],ma,mi;
void ready()
{
    fin>>n>>k;
    for (int i=1;i<=n;i++)
     {
       fin>>num[i];
       if (num[i]>ma) ma=num[i];
       rk[i]=(1 << num[i])-1;
     }
     if (ma>n)
      mi=n;
      else
      mi=ma;
}
bool chk(int rook[])
{
    for (int i=1;i<=n;i++)
      if (rook[i]!=0)
        return false;
    return true;
}
void poly(int dep,int lev,int pow)
{  
   int tmp[5];
  if (chk(rk))  //如果检查是空棋盘
   {
ans[0][dep]=1;   
     return;
   }
           
             memcpy(tmp,rk,sizeof(tmp));
             while (rk[lev]==0) lev++;
while ((rk[lev] & (1 << pow))!=(1 << pow))
  pow++;
rk[lev]=rk[lev]- (1 << pow);
             if (rk[lev]==0)
poly(dep+1,lev+1,0);
else poly(dep+1,lev,pow+1);
            for (int l=0;l<=mi;l++)
{ans[l][dep]+=ans[l][dep+1];
ans[l][dep+1]=0;}
memcpy(rk,tmp,sizeof(rk));
                rk[lev]=0;
             for (int k=lev+1;k<=n;k++)
              if ((rk[k])>=(1 << pow))
rk[k]=rk[k]- (1 << pow);
              poly(dep+1,lev+1,0);
            for (int l=1;l<=mi;l++)
{ans[l][dep]+=ans[l-1][dep+1];
ans[l-1][dep+1]=0;}
memcpy(rk,tmp,sizeof(rk));

         
}
int main()
{   fin.open("c:\\test.txt");
    ready();
    poly(1,1,0);
cout<<ans[k][1];
    fin.close();
}

2009年1月7日星期三

POJ 2449 A* search K shortest path

First real C++ program
#include<iostream>
#include<fstream>
using namespace std;
int n,m,s,t,k,size;
int l[1001],l2[1001],her[1001],time[1001];
bool used[1001];
fstream fin;
int a,b,r;
struct edge{
    int v,l,t;
};
struct key{
int v,value;
};

edge map[1001][1001],map2[1001][1001];
key data[1001],tmp;
void ready()
{
fin>>n>>m;
   for (int i=1;i<=m;i++)
   {  
  fin>>a>>b>>r;
  l[a]++;
      map[a][l[a]].v=b;
      map[a][l[a]].l=r;
      l2[b]++;
      map2[b][l2[b]].v=a;
      map2[b][l2[b]].l=r;
   }
   fin>>s>>t>>k;
   if (s==t) k++;
}
void dijkstra()
{ int z;
   for (int i=1;i<=n;i++)
her[i]=1000000;
   her[t]=0;
   for (int i=1;i<=n;i++)
   {
  int min=1000000;
  for (int j=1;j<=n;j++)
    if ((!used[j]) && (her[j]<min))
{
min=her[j];
z=j;
  }
used[z]=true;
for (int j=1;j<=l2[z];j++)
{
   if (her[z]+map2[z][j].l<her[map2[z][j].v])
            her[map2[z][j].v]=her[z]+map2[z][j].l;
}
   }
}
void push(int v,int i)
{    int tmp1;
     key temp;
    size++;
data[size].v=map[v][i].v;
data[size].value=tmp.value+map[v][i].l;
tmp1=size;
while (tmp1 > 1)
{
if (data[tmp1 >> 1].value+her[data[tmp1>>1].v]<data[tmp1].value+her[map[v][i].v]) break;
temp=data[tmp1];
data[tmp1]=data[tmp1 >> 1];
data[tmp1 >> 1]=temp;
        tmp1= tmp1 >> 1;
}
}
void del()
{   key temp;
temp=data[size];
data[size]=data[1];
data[1]=temp;
size--;
int i = 1;
while ((i << 1) <= size)
{
int j;
j = i << 1;
if ((j < size) && (data[j + 1].value+her[data[j+1].v]< data[j].value+her[data[j].v])) j++;
if (data[i].value+her[data[i].v]< data[j].value+her[data[j].v]) break;
temp=data[i];
data[i]=data[j];
data[j]=temp;
i = j;
}
}
int a_star()
if( her[s]==1000000 ) return -1;
data[1].v=s;
data[1].value=0;
  time[s]=0;
  size=1;
  
  while (size>0) {
    time[data[1].v]++;
 if (time[t]==k)
 return data[1].value;
 
      tmp=data[1];
 del();
 if (time[data[1].v]>k) continue;
 for (int e=1;e<=l[tmp.v];e++)
 {push(tmp.v,e);                           
  }
  }
return -1;
}
int main()
{
 fin.open("c:\\test.txt");
ready(); 
 dijkstra();
 int ans;
 ans=a_star();
 cout<<ans;  
 fin.close();
}