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