The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

浙大校赛 B题 暴力覆盖

之前想进行hash,发现思路非常麻烦。索性来个一一对应,找到第一个M后,扫描所有52个字母,一个字母正反各算一次,找准基准点后,用一张7*16的图进行覆盖,整张图要完全一一对应。 为了避免附近字母的干扰,先做一遍深搜,只对深搜搜过的点进行对应,其他的不管。
#include<iostream>
using namespace std;

char s[26][7][17]=
{
    
{
        
"111111MMM1111111",
        
"11111MM1MM111111",
        
"1111MM111MM11111",
        
"111MMMMMMMMM1111",
        
"11MM1111111MM111",
        
"1MMM11111111MM11",
        
"1MM1111111111MM1"
    }
,
    
{
        
"1MMMMMMMMMMM1111",
        
"1MM11111111MM111",
        
"1MM11111111MM111",
        
"1MMMMMMMMMMM1111",
        
"1MM11111111MM111",
        
"1MM11111111MM111",
        
"1MMMMMMMMMMM1111"
    }
,
    
{
        
"11111MMMMMMMM111",
        
"111MM1111111MM11",
        
"11MM111111111MM1",
        
"11MM111111111111",
        
"11MM111111111MM1",
        
"111MM1111111MM11",
        
"11111MMMMMMMM111"
    }
,
    
{
        
"1MMMMMMMMMMM1111",
        
"1MM111111111MM11",
        
"1MM1111111111MM1",
        
"1MM1111111111MM1",
        
"1MM1111111111MM1",
        
"1MM111111111MM11",
        
"1MMMMMMMMMMM1111"
    }
,
    
{
        
"1MMMMMMMMMMMM111",
        
"1MM1111111111111",
        
"1MM1111111111111",
        
"1MMMMMMMMMMMM111",
        
"1MM1111111111111",
        
"1MM1111111111111",
        
"1MMMMMMMMMMMM111"
    }
,
    
{
        
"1MMMMMMMMMMMMM11",
        
"1MM1111111111111",
        
"1MM1111111111111",
        
"1MMMMMMMMMMMMM11",
        
"1MM1111111111111",
        
"1MM1111111111111",
        
"1MM1111111111111"
    }
,
    
{
        
"11111MMMMMMMM111",
        
"111MM1111111MM11",
        
"11MM111111111MM1",
        
"11MM111111111111",
        
"11MM111111MMMMM1",
        
"111MM1111111MM11",
        
"11111MMMMMMMMM11"
    }
,
    
{
        
"1MM111111111MM11",
        
"1MM111111111MM11",
        
"1MM111111111MM11",
        
"1MMMMMMMMMMMMM11",
        
"1MM111111111MM11",
        
"1MM111111111MM11",
        
"1MM111111111MM11"
    }
,
    
{
        
"11111MMMMMM11111",
        
"1111111MM1111111",
        
"1111111MM1111111",
        
"1111111MM1111111",
        
"1111111MM1111111",
        
"1111111MM1111111",
        
"11111MMMMMM11111"
    }
,
    
{
        
"1111MMMMMMMM1111",
        
"1111111MM1111111",
        
"1111111MM1111111",
        
"1111111MM1111111",
        
"111MM11MM1111111",
        
"111MMM1MM1111111",
        
"11111MMMM1111111"
    }
,
    
{
        
"11MM111111MMM111",
        
"11MM11111MMM1111",
        
"11MM111MMM111111",
        
"11MMMMM111111111",
        
"11MM111MMM111111",
        
"11MM11111MMM1111",
        
"11MM111111MMMM11"
    }
,
    
{
        
"11MM111111111111",
        
"11MM111111111111",
        
"11MM111111111111",
        
"11MM111111111111",
        
"11MM111111111111",
        
"11MM111111111111",
        
"11MMMMMMMMMMMM11"
    }
,
    
{
        
"1MM1111111111MM1",
        
"1MMMM111111MMMM1",
        
"1MM1MM1111MM1MM1",
        
"1MM11MMMMM111MM1",
        
"1MM1111M11111MM1",
        
"1MM1111111111MM1",
        
"1MM1111111111MM1"
    }
,
    
{
        
"1MMM111111111MM1",
        
"1MMMM11111111MM1",
        
"1MM1MM1111111MM1",
        
"1MM11MM111111MM1",
        
"1MM1111MM1111MM1",
        
"1MM111111MMM1MM1",
        
"1MM11111111MMMM1"
    }
,
    
{
        
"11111MMMMMM11111",
        
"111MMM1111MMM111",
        
"11MMM111111MMM11",
        
"1MM1111111111MM1",
        
"11MMM111111MMM11",
        
"111MMM1111MMM111",
        
"11111MMMMMM11111"
    }
,
    
{
        
"1MMMMMMMMMMM1111",
        
"1MM111111111MM11",
        
"1MM1111111111MM1",
        
"1MM111111111MM11",
        
"1MMMMMMMMMMM1111",
        
"1MM1111111111111",
        
"1MM1111111111111"
    }
,
    
{
        
"11111MMMMMM11111",
        
"111MMM1111MMM111",
        
"11MMM111111MMM11",
        
"1MM1111111111MM1",
        
"11MMM1MMMM1MMM11",
        
"111MMM11MMMMM111",
        
"111111MMMM1MMMM1"
    }
,
    
{
        
"1MMMMMMMMMMM1111",
        
"1MM111111111MM11",
        
"1MM1111111111MM1",
        
"1MM111111111MM11",
        
"1MMMMMMMMMMM1111",
        
"1MM11111111MM111",
        
"1MM111111111MMM1"
    }
,
    
{
        
"1111MMMMMMMM1111",
        
"111MM1111111MM11",
        
"11MMM1111111MMM1",
        
"1111MMMMM1111111",
        
"1MMM111MMMM11111",
        
"111MMM11111MMM11",
        
"11111MMMMMMM1111"
    }
,
    
{
        
"11MMMMMMMMMMMM11",
        
"11MMMMMMMMMMMM11",
        
"1111111MM1111111",
        
"1111111MM1111111",
        
"1111111MM1111111",
        
"1111111MM1111111",
        
"1111111MM1111111"
    }
,
    
{
        
"1MM1111111111MM1",
        
"1MM1111111111MM1",
        
"1MM1111111111MM1",
        
"1MM1111111111MM1",
        
"1MMM11111111MMM1",
        
"1MMM11111111MMM1",
        
"111MMMMMMMMMM111"
    }
,
    
{
        
"1MMMM111111MMMM1",
        
"11MMM111111MMM11",
        
"11MMM111111MMM11",
        
"111MMM1111MMM111",
        
"1111MMM11MMM1111",
        
"11111MM11MM11111",
        
"111111MMMM111111"
    }
,
    
{
        
"1MM1111111111MM1",
        
"1MM1111111111MM1",
        
"11MM111MM111MM11",
        
"11MM111MM111MM11",
        
"11MM111MM111MM11",
        
"11MM1MM11MM1MM11",
        
"111MMM1111MMM111"
    }
,
    
{
        
"11MMM111111MMM11",
        
"111MMM1111MMM111",
        
"1111MMM11MMM1111",
        
"111111MMMM111111",
        
"1111MMM11MMM1111",
        
"111MMM1111MMM111",
        
"11MMM111111MMM11"
    }
,
    
{
        
"11MMM111111MMM11",
        
"111MMM1111MMM111",
        
"1111MMM11MMM1111",
        
"111111MMMM111111",
        
"1111111MM1111111",
        
"1111111MM1111111",
        
"1111111MM1111111"
    }
,
    
{
        
"111MMMMMMMMMM111",
        
"1111111111MM1111",
        
"111111111MM11111",
        
"11111111MM111111",
        
"111111MM11111111",
        
"11111MM111111111",
        
"111MMMMMMMMMMM11"
    }
,
}
;

int n,m;
char rs[26][7][17];
char map[1000][1000];
int dp[30];
int dir[8][2]={{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{1,-1},{-1,1},{1,1}};
int v[1000][1000];
bool god(int x,int y)
{

    
if(x>=0&&x<n&&y>=0&&y<m)
        
return true;
    
else
        
return false;
}

int num=0;
void dfs(int x,int y)
{
    v[x][y]
=num;
    
int i;
    
for(i=0;i<8;i++)
    
{
        
int nx=x+dir[i][0];
        
int ny=y+dir[i][1];
        
if(god(nx,ny)&&map[nx][ny]=='M'&&v[nx][ny]==0)
            dfs(nx,ny);
    }

}

void init()
{

    
int i,j,k;
    
for(i=0;i<26;i++)
        
for(j=0;j<7;j++)
            
for(k=0;k<16;k++)
            
{
                rs[i][j][k]
=s[i][6-j][15-k];
            }

}


bool match(int x,int y,int i)
{
    
int flag=1;
    
int sx=0,sy=0;
    
int j,k;
    
for(j=0;j<16;j++)
    
{
        
if(s[i][0][j]=='M'){sx=x;sy=y-j;break;}
    }

    
for(j=0;j<7;j++)
    
{

        
for(k=0;k<16;k++)
        
{

            
if((s[i][j][k]=='M'&&map[sx+j][sy+k]!='M')||(v[sx+j][sy+k]==num&&s[i][j][k]!='M'&&map[sx+j][sy+k]=='M') )
            
{
                flag
=0;
                
break;
            }

        }

    }

    
if(flag==1)
        
return true;
    
for(j=0;j<16;j++)
    
{
        
if(rs[i][0][j]=='M'){sx=x;sy=y-j;break;}
    }


    
for(j=0;j<7;j++)
    
{
        
for(k=0;k<16;k++)
        
{
            
if(  (rs[i][j][k]=='M'&&map[sx+j][sy+k]!='M')||(v[sx+j][sy+k]==num&&rs[i][j][k]!='M'&&map[sx+j][sy+k]=='M')) 
                
return false;
                
        }

    }

    
return true;
}

void input()
{

    
int i;
    
for(i=0;i<n;i++)
        scanf(
"%s",map[i]);
}


int main()
{
    init();
    
while(scanf("%d%d",&n,&m)!=EOF)
    
{
        num
=0;
        memset(v,
0,sizeof(v));
        memset(dp,
0,sizeof(dp));
        memset(map,
0,sizeof(map));
        input();

        
int i,j;
        
for(i=0;i<n;i++)
        
{
            
for(j=0;j<m;j++)
            
{

                
if(map[i][j]=='M'&&v[i][j]==0)
                
{
                    num
++;
                    dfs(i,j);
                    
int k;
                    
for(k=0;k<26;k++)
                    
{
                        
//if(k==8)
                        
//    __asm int 3;

                        
if(match(i,j,k))
                        
{
                            dp[k]
=1;
                            num
++;
                            
break;
                        }

                        
                    }

                }

            }

        }

        
for(i=0;i<26;i++)
        
{
            
if(dp[i]==1)
                printf(
"%c",i+'A');
        }

        printf(
"\n");

    }

    
return 0;
}

posted on 2010-04-10 22:44 abilitytao 阅读(1372) 评论(0)  编辑 收藏 引用


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