2013 Asia acm Hangzhou Regional Contest 杭州现场赛

Ｂ Stealing Harry Potter's Precious

题目大意:给定一个n*m的地图，某些点可以走，某些点可以走某些点不可以走，给定一个起点，又给出了k个点k<=4，要求从起点经过Ｋ个点最短的长度是多少

思路:给每个点标定状态为[x][y][state]，state是压缩状态的已经走过需要走过点的集合，然后bfs一下即可

 #include<cstdio>

 #include<queue>

 #include<cstring>

 #define maxn 101

 using namespace std;

 const int dx[]={,,,,-};

 const int dy[]={,,-,,};

 int map[maxn][maxn],full,n,m,sx,sy,x,y,ma;

 char ch[maxn];

 struct T{int x;int y;int st;int dist;};

 int cal(int x,int y){if(y<=)return x;return x|(<<(y-));}

 bool visit[maxn][maxn][];

 int bfs(int x,int y)

 {

         queue<T>q;T a;

         a.x=x;a.y=y;a.st=cal(,map[x][y]);a.dist=;

         visit[a.x][a.y][a.st]=;

         q.push(a);

         while(!q.empty())

         {

                 T u=q.front();

                 q.pop();

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

                 {

                         int xx=u.x+dx[i],yy=u.y+dy[i];

                         if(xx<||xx>n||yy<||yy>m||map[xx][yy]==)continue;

                         T v;v.x=xx;v.y=yy;

                         v.st=cal(u.st,map[xx][yy]);

                         v.dist=u.dist+;

                         if(visit[v.x][v.y][v.st]==)continue;

                         visit[v.x][v.y][v.st]=;

                         if(v.st==full)

                         {

                                 return v.dist;

                         }

                         q.push(v);

                 }

         }

         return -;

 }

 int main()

 {

         while(scanf("%d%d",&n,&m)!=EOF)

         {

                 memset(visit,,sizeof(visit));

                 if(n== && m==)break;

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

                 {

                         scanf("%s",ch+);

                         for(int j=;j<=m;j++)

                         {

                                 if(ch[j]=='#')map[i][j]=;else map[i][j]=;

                                 if(ch[j]=='@')sx=i,sy=j;

                         }

                 }

                 int k;

                 scanf("%d",&k);

                 full=(<<k)-;

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

                 {

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

                         map[x][y]=i+;

                 }

                 printf("%d\n",bfs(sx,sy));

         }

     return ;

 }

C - Zhuge Liang's Password

题目大意:给出两个矩阵，要求两个矩阵旋转之后的最大重合的数字个数

思路:直接模拟

 #include<cstdio>

 #include<queue>

 #include<cstring>

 #define maxn 101

 using namespace std;

 int a[maxn][maxn],n,b[maxn][maxn];

 void rot(){

         int c[maxn][maxn]={{}};

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

                 for(int j=;j<=n;j++)c[i][j]=a[j][n-i+];

         memcpy(a,c,sizeof(a));

 }

 int main()

 {

         while(scanf("%d",&n)!=EOF){

                 if(n==)break;

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

                         for(int j=;j<=n;j++)scanf("%d",&a[i][j]);

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

                         for(int j=;j<=n;j++)scanf("%d",&b[i][j]);

                 int ans=;

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

                         int temp=;

                         rot();

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

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

                                         if(a[i][j]==b[i][j])temp++;

                         ans=max(ans,temp);

                 }

                 printf("%d\n",ans);

         }

     return ;

 }

巴特西

2013 Asia acm Hangzhou Regional Contest 杭州现场赛

最新文章

热门文章