现在的位置: 首页 > 综合 > 正文

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;
}

抱歉!评论已关闭.