Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

POJ 1242 Plugged In---模拟

Posted on 2010-03-13 15:21 Uriel 阅读(274) 评论(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;
}


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理