正文

【BZOJ 4148】 4148: [AMPPZ2014]Pillars （乱搞）

IP云
IP云V管理员/0 阅读
11/28
小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

4148: [AMPPZ2014]Pillars

Time Limit: 5 Sec  Memory Limit: 256 MBSec  Special Judge
Submit: 100  Solved: 49

Description
给定一个n*m的矩形，其中有f个2*2的障碍物，其中任意两个障碍物中心之间的欧几里得距离至少为6，
且每个障碍物的中心到边缘的距离至少为3。请找到一条从左下角(1,1)出发经过所有没有障碍物的点各
一次的且最后回到左下角的回路。

Input
第一行包含三个整数n,m,f(1<=n,m<=1000且n,m都为偶数)。
接下来f行，每行两个整数x,y(1<=x<n,1<=y<m)，表示该障碍物左下角的坐标。

Output
如果无解，输出NIE，否则第一行输出TAK，第二行输出方案。
方案包含n*m-4*f个字符，第i个字符表示第i步的移动方向，用G表示上，D表示下，L表示左，P表示右。

Sample Input
12 6 2
3 3
9 3

Sample Output
TAK
PPPPPPPPPPPGGGLDDLLLLLGPPGLLLDDLLLGGGPPPPPPPPPPGLLLLLLLLLLLDDDDD

HINT

Source

鸣谢Claris上传

【分析】

唉。。乱搞的水题我都是不会。。

就是随便弄一条路出来，然后绕开障碍。

大概就是这样绕开：

理解了好久。。 

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 char a[][];

 int main()

 {

     int n,m,k;

     scanf("%d%d%d",&n,&m,&k);

     for(int i=;i<=n;i++)

      for(int j=;j<=m;j++) a[i][j]=i&?'D':'G';

     for(int i=;i<=n;i+=) a[i][]='L';

     for(int i=;i<=n;i+=) a[i][m]='L';

     for(int i=;i<n;i++) a[i][]='P';

     for(int i=;i<=k;i++)

     {

         int x,y;

         scanf("%d%d",&x,&y);

         if(x&)

         {

             a[x+][y-]='L';

             a[x][y+]='P';

             a[x+][y+]='P';

             a[x+][y+]='L';

         }

         else

         {

             if(y==)

             {

                 a[x][]='G';

                 a[x][]='P';

                 a[x+][]='D';

                 a[x+][y+]='L';

             }

             else

             {

                 a[x+][y+]='L';

                 a[x][y-]='P';

                 a[x+][y-]='P';

                 a[x+][y-]='L';

             }

         }

       }

       printf("TAK\n");

       int xx=,yy=,nw=n*m-*k;

       while(nw--)

       {

           printf("%c",a[xx][yy]);

            if(a[xx][yy]=='L') xx--;

           else if(a[xx][yy]=='P') xx++;

           else if(a[xx][yy]=='D') yy--;

           else yy++;

       }

     return ;

 }

2017-04-10 08:53:03

相关阅读

目录[+]