Posted on 2010-03-13 15:21
Uriel 閱讀(277)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
POJ 、
模擬
是個(gè)非常簡(jiǎn)單的模擬，前天weekly只有LP大牛一人在最后才出所以題都沒(méi)看。。
今天題讀了好一會(huì)兒發(fā)現(xiàn)意思其實(shí)很簡(jiǎn)單。。pins和holes的匹配。。奇怪的是POJ上AC的人數(shù)也是難以想象的少。。
先正面匹配，依次順時(shí)針旋轉(zhuǎn)0度，90度，180度，270度，再反面，也是依次順時(shí)針旋轉(zhuǎn)0度，90度，180度，270度，選取最小值
但是還是被水題蹂躪。。先是a，b兩數(shù)組開小 ( 以為m也是最大100。。)，然后是abs老問(wèn)題。。用C++交CE。。然后換G++，因?yàn)镚++我還寫的%.4lf又WA。。交了有10次才過(guò)。。悲劇啊。。
丑陋的代碼見下，這是在POJ上AC的。。要想在EOJ上AC需要改為最后一個(gè)case后面不空行。。( EOJ都這個(gè)格式么。。跟1241一樣因?yàn)檫@個(gè)空行問(wèn)題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;
}