topcoder SRM 736 Div2 1000

1000:MazeWithKeys

题意:

给出一个图,图中有几种符号:

  • “ . ”表示当前位置是空地。。。
  • “ # ”表示当前位置是墙。。。
  • “ * ”表示终点。
  • 小写字母是钥匙,每种钥匙只能打开对应的大写字母的门。
  • 大写字母是铁门,每种门最多只有一个。

对于一个地图,你想要知道有多少的空地可以到达出口,为了使游戏显得不那么简单,你想要知道到达出口至少开一扇门的的空地有多少个。

分析:

因为这个图最大只有50*50,所以我们可以直接爆搜,当你找到一个钥匙时,判断是否有匹配的门,当你找到门时,看看有没有钥匙,然后爆搜就好了。。。然后题目有毒,至少一个表示不用开门的不符合条件。。。

代码:

int n,m,tox,toy,ans,flag;
char Map[55][55];
int vis[55][55],to[55][55];
int men[30],key[30];
struct Men{int x,y;}M[30];
int dx[]={0,1,-1,0,0};
int dy[]={0,0,0,1,-1};
void dfs(int x,int y)
{
    if(vis[x][y]==1||Map[x][y]=='#')
        return;
    if(xn||y>m||y<=0)
        return;
    if(65<=Map[x][y]&&Map[x][y]<=90)
    {
        men[Map[x][y]-64]=1;
        if(key[Map[x][y]-64]==1)
        {
            vis[x][y]=1;flag=1;
            for(int i=1;i=97&&Map[x][y]<=122)
    {
        key[Map[x][y]-96]=1;
        if(men[Map[x][y]-96]==1)
        {
            flag=1;
            dfs(M[Map[x][y]-96].x,M[Map[x][y]-96].y);
        }
    }
    for(int i=1;i<=4;i++)
        dfs(x+dx[i],y+dy[i]);
}
void dfs_ans(int x,int y,int k)
{
    if(Map[x][y]!='.'||xn||y>m||y<=0||to[x][y]==1)
        return;
    if(k==1) ans++;
    to[x][y]=1;                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                             
    for(int i=1;i<=4;i++)
        dfs_ans(x+dx[i],y+dy[i],k);
}
void dfs_GG(int x,int y)
{
    if(vis[x][y]==1||(Map[x][y]!='.'&&Map[x][y]!='*'&&Map[x][y]<97))
        return;
    if(xn||y>m||y<=0)
        return;
    vis[x][y]=1;
    for(int i=1;i<=4;i++)
        dfs_GG(x+dx[i],y+dy[i]);
}
int MazeWithKeys::startingPoints(vector  a) {
	memset(Map,0,sizeof(Map));
	memset(to,0,sizeof(to));
	ans=0;
	n=a.size(),m=a[0].size();
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            Map[i+1][j+1]=a[i][j];
            if(65<=a[i][j]&&a[i][j]<=90)
                M[a[i][j]-64].x=i+1,M[a[i][j]-64].y=j+1;
            if(a[i][j]=='*')
                tox=i+1,toy=j+1;
        }
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(!to[i][j]&&Map[i][j]=='.')
            {
                memset(vis,0,sizeof(vis));
                memset(men,0,sizeof(men));
                memset(key, 0,sizeof(key));
                dfs_GG(i,j);
                if(vis[tox][toy]==1)
                    dfs_ans(i,j,0);
                else
                {
                    memset(vis,0,sizeof(vis));
                    flag=0;dfs(i,j);
                    if(vis[tox][toy]==1&&flag==1)
                        dfs_ans(i,j,1);
                    else dfs_ans(i,j,0);
                }
            }
    return ans;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注