## UVA – 1102(vector没有find用法)

2019年04月04日 ⁄ 综合 ⁄ 共 2675字 ⁄ 字号 评论关闭
```#include<cstring>
#include <cstdio>
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;

const int maxn = 200+10;
const int maxm = 50*4+10;
int maze[maxn][maxm],n,m,vis[maxn][maxm];
char str[maxn*2];

struct node{
int x,y;
node(int x=0,int y=0):x(x),y(y){}
bool operator < (const node& rhs) const{
return x < rhs.x || x == rhs.x && y<rhs.y;
}
};
struct Black{
vector<node> side;
char symbol;
int num;
Black():num(0){}
};
struct White{
vector<node> side;
};

const char* st="WAKJSD";
bool find(vector<node>& a,node& v){
vector<node> ::iterator p;
p=lower_bound(a.begin(),a.end(),v);
if(p!=a.end()&&p->x==v.x&&p->y==v.y) return true;
return false;
}
const int dx[]={0,0,-1,1};
const int dy[]={1,-1,0,0};
void dfs_black(int x,int y,Black& temp){
for(int i=0;i<4;i++){
int nx=x+dx[i],ny=y+dy[i];
if(maze[nx][ny]==1&&!vis[nx][ny]){
vis[nx][ny]=1;
temp.side.push_back(node(nx,ny));
dfs_black(nx,ny,temp);
}
}
}
void dfs_white(int x,int y,White& temp){
for(int i=0;i<4;i++){
int nx=x+dx[i],ny=y+dy[i];
if(maze[nx][ny]==0&&!vis[nx][ny]){
vis[nx][ny]=1;
dfs_white(nx,ny,temp);
}
else if(maze[nx][ny]==-1||maze[nx][ny]==1){
temp.side.push_back(node(nx,ny));
}
}
}
int main()
{
for(int i=0;i<maxm;i++) maze[i][0]=-1;
for(int i=0;i<maxn;i++) maze[0][i]=-1;
int kase=1;
while(scanf("%d %d",&n,&m)==2){
if(!n&&!m) break;
gets(str);
for(int i=1;i<=n;i++){
gets(str);
for(int j=0,k=1;j<m;j++,k+=4){
int num;
switch(str[j]){
case '0':num=0; break; case '1':num=1; break;
case '2':num=2; break; case '3':num=3; break;
case '4':num=4; break; case '5':num=5; break;
case '6':num=6; break; case '7':num=7; break;
case '8':num=8; break; case '9':num=9; break;
case 'a':num=10; break; case 'b':num=11; break;
case 'c':num=12; break; case 'd':num=13; break;
case 'e':num=14; break; case 'f':num=15; break;
}
for(int l=0;l<=3;l++){
int te=(num>>l)&1;
maze[i][k+3-l]=te;
}
}
}
for(int i=0;i<maxm;i++) maze[n+1][i]=-1;
for(int i=0;i<maxn;i++) maze[i][m*4+1]=-1;
void show();
// show();

int lim=4*m;
vector<Black> black;
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++){
for(int j=1;j<=lim;j++){
if(maze[i][j]==1&&!vis[i][j]){
Black temp;
temp.side.push_back(node(i,j)); vis[i][j]=1;
dfs_black(i,j,temp);
black.push_back(temp);
}
}
}
for(int i=0;i<black.size();i++){
sort(black[i].side.begin(),black[i].side.end());
}

vector<White> white;
for(int i=1;i<=n;i++){
for(int j=1;j<=lim;j++){
if(maze[i][j]==0&&!vis[i][j]){
White temp;
vis[i][j]=1;
dfs_white(i,j,temp);
white.push_back(temp);
}
}
}
for(int i=0;i<white.size();i++){
vector<node>& w = white[i].side;
for(int j=0;j<black.size();j++){
vector<node>& b = black[j].side;
int ok=1;
for(int k=0;k<w.size();k++){
if(!find(b,w[k])){
ok=0; break;
}
}
if(ok){
black[j].num++; break;
}
}
}
printf("Case %d: ",kase); kase++;
vector<char> ans;
for(int i=0;i<black.size();i++){
ans.push_back(st[black[i].num]);
}
sort(ans.begin(),ans.end());
for(int i=0;i<ans.size();i++) printf("%c",ans[i]);
printf("\n");
}
return 0;
}
```