Posted on 2010-03-13 15:21
Uriel 阅读(269)
评论(0) 编辑 收藏 引用 所属分类:
POJ 、
模拟
是个非常简单的模拟，前天weekly只有LP大牛一人在最后才出所以题都没看。。
今天题读了好一会儿发现意思其实很简单。。pins和holes的匹配。。奇怪的是POJ上AC的人数也是难以想象的少。。
先正面匹配，依次顺时针旋转0度，90度，180度，270度，再反面，也是依次顺时针旋转0度，90度，180度，270度，选取最小值
但是还是被水题蹂躏。。先是a，b两数组开小 ( 以为m也是最大100。。)，然后是abs老问题。。用C++交CE。。然后换G++，因为G++我还写的%.4lf又WA。。交了有10次才过。。悲剧啊。。
丑陋的代码见下，这是在POJ上AC的。。要想在EOJ上AC需要改为最后一个case后面不空行。。( EOJ都这个格式么。。跟1241一样因为这个空行问题PE。。)
/**//*
Problem: 1242 User: Uriel
Memory: 708K Time: 16MS
Language: G++ Result: Accepted */
#include<stdio.h>
#include<stdlib.h>
using namespace std;
struct M
{
int x,y;
};
M S[20000],O[20000];
int n,m,res,MIN;
int map[110][110],tmpmap[110][110],a[20000],b[20000];
void InitPlug_front()
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
S[(i-1)*n+j].x=i;
S[(i-1)*n+j].y=j;
map[i][j]=(i-1)*n+j;
O[(i-1)*n+j].x=i;
O[(i-1)*n+j].y=j;
}
}
return ;
}
void InitPlug_back()
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
S[(i-1)*n+(n-j+1)].x=i;
S[(i-1)*n+(n-j+1)].y=j;
map[i][j]=(i-1)*n+n-j+1;
}
}
return ;
}
void Rotate()
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
tmpmap[j][n-i+1]=map[i][j];
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
map[i][j]=tmpmap[i][j];
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
S[map[i][j]].x=i;
S[map[i][j]].y=j;
}
}
}
int main()
{
int cse=1;
int i,j;
while(scanf("%d",&n),n)
{
scanf("%d",&m);
for(i=0;i<m;i++)
{
scanf("%d %d",&a[i],&b[i]);
}
InitPlug_front();//-------------Init Map-front
res=0;
MIN=0x7fffffff;
for(i=0;i<m;i++)
{
res+=abs(S[b[i]].x-O[a[i]].x)+abs(S[b[i]].y-O[a[i]].y);
}
if(res<MIN)MIN=res;
Rotate();//---------------90 degree clockwise
res=0;
for(i=0;i<m;i++)
{
res+=abs(S[b[i]].x-O[a[i]].x)+abs(S[b[i]].y-O[a[i]].y);
}
if(res<MIN)MIN=res;
Rotate();//---------------180 degree clockwise
res=0;
for(i=0;i<m;i++)
{
res+=abs(S[b[i]].x-O[a[i]].x)+abs(S[b[i]].y-O[a[i]].y);
}
if(res<MIN)MIN=res;
Rotate();//---------------270 degree clockwise
res=0;
for(i=0;i<m;i++)
{
res+=abs(S[b[i]].x-O[a[i]].x)+abs(S[b[i]].y-O[a[i]].y);
}
if(res<MIN)MIN=res;
InitPlug_back();//-------------Init Map-back
res=0;
for(i=0;i<m;i++)
{
res+=abs(S[b[i]].x-O[a[i]].x)+abs(S[b[i]].y-O[a[i]].y);
}
if(res<MIN)MIN=res;
Rotate();//---------------90 degree clockwise
res=0;
for(i=0;i<m;i++)
{
res+=abs(S[b[i]].x-O[a[i]].x)+abs(S[b[i]].y-O[a[i]].y);
}
if(res<MIN)MIN=res;
Rotate();//---------------180 degree clockwise
res=0;
for(i=0;i<m;i++)
{
res+=abs(S[b[i]].x-O[a[i]].x)+abs(S[b[i]].y-O[a[i]].y);
}
if(res<MIN)MIN=res;
Rotate();//---------------270 degree clockwise
res=0;
for(i=0;i<m;i++)
{
res+=abs(S[b[i]].x-O[a[i]].x)+abs(S[b[i]].y-O[a[i]].y);
}
if(res<MIN)MIN=res;
printf("Scenario %d: smallest average = %.4f\n\n",cse++,1.0*(MIN+m)/(1.0*m));
}
// system("PAUSE");
return 0;
}