哈尔滨赛区热身赛 A题

本文主要是介绍哈尔滨赛区热身赛 A题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

数据量很小可以搜索，注意对u=1时要特殊处理，否则超时

#include<iostream>
#include<math.h>
using namespace std;
bool map[10][10];
int a[30],n,m,ans,time;
int s[7]={0,25,7,3,3,1};
int min(int x,int y)
{
if (x<y) return x;
else return y;
}
int sa(int u)
{
int i,j,c;
c=0;
for(i=u;i>=1;i--)
{
   for(j=1;j<=a[i];j++)
   {
c++;
    if (c>=s[i]) return c;
   }
}
return 1000;
}
bool judge()
{
int i,j;
for(i=1;i<=n;i++)
   for(j=1;j<=m;j++)
     if (!map[i][j]) return false;
   return true;
}
void oper(int x,int y,int u)
{
int i,j;
u--;
for(i=-u;i<=u;i++)
   for(j=-u;j<=u;j++)
    if ( (abs(i)+abs(j)<=u) && (x+i>=1) && (x+i<=n) && (y+j>=1) && (y+j<=m) )
      map[x+i][y+j]=true;
}
int need()
{
int sum,i,j;
sum=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if (!map[i][j]) sum++;
return sum;
}
int dfs(int u,int v)
{
   int i,j,k,temp[10][10],s,t,g;
   bool fl;
   ans=min(ans,sa(u));
// if (time>1000) return 0;
   //time++;
    //if (judge())
// ans=min(ans,v);
   if (u==1)
   {
    g=need();
if (g>a[u]) return 0;
else
{
      ans=min(ans,g+v);
   return 0;
}
   }
   if (v>ans) return 0;
   while((a[u]==0)&&(u>0)) u--;
   if (u==0) return 0;

fl=true;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
temp[i][j]=map[i][j];

   for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
     if (!map[i][j])
{
     fl=false;
oper(i,j,u);
a[u]--;
if (judge())
   ans=min(ans,v+1);
   else
     dfs(u,v+1);
a[u]++;
for(s=1;s<=n;s++)
      for(t=1;t<=m;t++)
        map[s][t]=temp[s][t];
}
if (fl) if (v<ans) ans=v;

}
int main()
{
int k,i,t,u,v,maxu,time;
while(cin>>n>>m>>k)
{
    memset(map,false,sizeof(map));
memset(a,0,sizeof(a));
maxu=0;time=0;
for(i=1;i<=k;i++)
{
     cin>>u>>v;
     a[u]+=v;
if (u>maxu) maxu=u;
}
if (maxu>=5) cout<<"1"<<endl;
else
{
ans=1000;
dfs(maxu,0);
if (ans==1000) cout<<"impossible"<<endl;
else cout<<ans<<endl;
}
}