The Fourth Dimension Space

枯葉北風寒，忽然年以殘，念往昔，語默心酸。二十光陰無一物，韶光賤，寐難安；不畏形影單，道途阻且慢，哪曲折，如渡飛湍。斬浪劈波酬壯志，同把酒，共言歡！ -如夢令

統(tǒng)計

隨筆 - 414
文章 - 13
評論 - 521
引用 - 0

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

CMU CV Group

友情鏈接

n皇后問題精彩分析
RMQ問題的精彩文章
開關(guān)燈問題

搜索

閱讀排行榜

評論排行榜

浙大校賽 B題暴力覆蓋

之前想進行hash,發(fā)現(xiàn)思路非常麻煩。索性來個一一對應(yīng)，找到第一個M后，掃描所有52個字母，一個字母正反各算一次，找準基準點后，用一張7*16的圖進行覆蓋，整張圖要完全一一對應(yīng)。為了避免附近字母的干擾，先做一遍深搜，只對深搜搜過的點進行對應(yīng)，其他的不管。

#include<iostream>

using namespace std;

char s[26][7][17]=

{

"111111MMM1111111",

"11111MM1MM111111",

"1111MM111MM11111",

"111MMMMMMMMM1111",

"11MM1111111MM111",

"1MMM11111111MM11",

"1MM1111111111MM1"

},

{

"1MMMMMMMMMMM1111",

"1MM11111111MM111",

"1MMMMMMMMMMM1111",

"1MM11111111MM111",

"1MMMMMMMMMMM1111"

},

{

"11111MMMMMMMM111",

"111MM1111111MM11",

"11MM111111111MM1",

"11MM111111111111",

"11MM111111111MM1",

"111MM1111111MM11",

"11111MMMMMMMM111"

},

{

"1MMMMMMMMMMM1111",

"1MM111111111MM11",

"1MM1111111111MM1",

"1MM111111111MM11",

"1MMMMMMMMMMM1111"

},

{

"1MMMMMMMMMMMM111",

"1MM1111111111111",

"1MMMMMMMMMMMM111",

"1MM1111111111111",

"1MMMMMMMMMMMM111"

},

{

"1MMMMMMMMMMMMM11",

"1MM1111111111111",

"1MMMMMMMMMMMMM11",

"1MM1111111111111",

"1MM1111111111111"

},

{

"11111MMMMMMMM111",

"111MM1111111MM11",

"11MM111111111MM1",

"11MM111111111111",

"11MM111111MMMMM1",

"111MM1111111MM11",

"11111MMMMMMMMM11"

},

{

"1MM111111111MM11",

"1MMMMMMMMMMMMM11",

"1MM111111111MM11",

"1MM111111111MM11"

},

{

"11111MMMMMM11111",

"1111111MM1111111",

"11111MMMMMM11111"

},

{

"1111MMMMMMMM1111",

"1111111MM1111111",

"111MM11MM1111111",

"111MMM1MM1111111",

"11111MMMM1111111"

},

{

"11MM111111MMM111",

"11MM11111MMM1111",

"11MM111MMM111111",

"11MMMMM111111111",

"11MM111MMM111111",

"11MM11111MMM1111",

"11MM111111MMMM11"

},

{

"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",

"1111111MM1111111",

"1111111MM1111111"

},

{

"1MM1111111111MM1",

"1MMM11111111MMM1",

"111MMMMMMMMMM111"

},

{

"1MMMM111111MMMM1",

"11MMM111111MMM11",

"111MMM1111MMM111",

"1111MMM11MMM1111",

"11111MM11MM11111",

"111111MMMM111111"

},

{

"1MM1111111111MM1",

"11MM111MM111MM11",

"11MM1MM11MM1MM11",

"111MMM1111MMM111"

},

{

"11MMM111111MMM11",

"111MMM1111MMM111",

"1111MMM11MMM1111",

"111111MMMM111111",

"1111MMM11MMM1111",

"111MMM1111MMM111",

"11MMM111111MMM11"

},

{

"11MMM111111MMM11",

"111MMM1111MMM111",

"1111MMM11MMM1111",

"111111MMMM111111",

"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 閱讀(1406) 評論(0) 編輯收藏引用

只有注冊用戶登錄后才能發(fā)表評論。




網(wǎng)站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

The Fourth Dimension Space

導航

統(tǒng)計

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

友情鏈接

搜索

最新評論

閱讀排行榜

評論排行榜

浙大校賽 B題暴力覆蓋

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

The Fourth Dimension Space

導航

統(tǒng)計

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

友情鏈接

搜索

最新評論

閱讀排行榜

評論排行榜

浙大校賽 B題 暴力覆蓋

浙大校賽 B題暴力覆蓋