Hdu 5025 Saving Tang Monk (BFS 2014 Guangzhou Online )

傷城~ 2022-08-12 06:58 83阅读 0赞

今天得知还有人关注着自己的博客，真是受宠若惊。

网赛的时候一开始没想透彻，贡献了几个WA。。。

这场网赛原题略多……不过也正是这样给了我们这种弱校一点机会。

从去年PKU的校赛开始就被树链剖分虐，一直虐到现在，决定抽时间好好学一下！

最多只有5个敌人，可以用int型变量的每一位01表示哪些被打败。

因为是求最快时间，所以用优先队列，不知道普通队列行不行……

用来判重的数组开了三层，可能有更好的方法吧，等围观过别人的题解再回来优化。

#include <iostream>
    #include <queue>
    #include <cstdio>
    #include <string>
    #include <cstring>
    using namespace std;
    
    const int N=105;
    
    char g[N][N];
    int where[N][N];
    bool visit[11][N][N]; //每把钥匙对应一维访问信息
    int n,m,tot;
    int x[10];
    int y[10];
    
    int dx[4] = {1,-1,0,0};
    int dy[4] = {0,0,1,-1};
    
    struct Node
    {
    	int x,y,time,id,state; //id 现在拿到几把钥匙
    	bool operator < (Node b) const
    	{
    		return time>b.time;
    	}
    }s;
    
    bool OK (Node a)
    {//是否是墙,本轮是否访问
    	if (visit[a.id][a.x][a.y]==false && g[a.x][a.y]!='#')
            return true;
    	return false;
    }
    
    bool Judge (Node &a)
    {//过去是否访问
        int name=where[a.x][a.y];
        if (a.state & 1<<(name-1) ) //杀过
            return true;
        else
        {
            a.state=a.state | 1<<(name-1);
            return false;
        }
    
    }
    
    int BFS ()
    {
    	int cnt=0;
    	priority_queue<Node> q;
    	q.push(s);
    	while (!q.empty())
    	{
    		Node cur = q.top();
    		q.pop();
    		if (g[cur.x][cur.y] == 'T' && cur.id==m)
    		{
    			cnt = cur.time;
    			break;
    		}
    		for (int i=0;i<4;i++)
    		{
    		    Node temp;
    			temp.x=cur.x+dx[i];
    			temp.y=cur.y+dy[i];
    			temp.time=cur.time+1;
    			temp.id=cur.id;
    			temp.state=cur.state;
    			if (OK(temp))
    			{
    				visit[temp.id][temp.x][temp.y]=true;
    				if (g[temp.x][temp.y]=='S' && Judge(temp)==false)
                        temp.time+=1;  //蛇被杀死
                    if (temp.id+1 == g[temp.x][temp.y]-'0' && temp.id+1<=m)
                    {
                         temp.id++; //拿钥匙
                         visit[temp.id][temp.x][temp.y]=true;
                    }
    				q.push(temp);
    			}
    		}
    	}
    	return cnt;
    }
    
    int main ()
    {
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
    	while (scanf("%d%d",&n,&m),n||m)
    	{
    		memset(g,'#',sizeof(g));
    		memset(visit,false,sizeof(visit));
    		memset(where,0,sizeof(where));
    		tot=0;//蛇的总数
    		for (int i=1;i<=n;i++)
    		{
    			scanf("%s",&g[i][1]);
    			g[i][n+1]='#';    //
    			for (int j=1;j<=n;j++)
                {
    				if (g[i][j]=='K')
    				{
    					s.x=i;
    					s.y=j;
    					s.time=0;
    					s.id=0;
    					s.state=0;
    					visit[0][s.x][s.y]=true;
    				}
    				if (g[i][j]=='S')
                    {
                        tot++;
                        where[i][j]=tot;
                        x[tot]=i;
                        y[tot]=j;
                    }
                }
    		}
    		int ans=BFS();
    		if (ans)
    			printf("%d\n",ans);
    		else
    			printf("impossible\n");
    	}
    	return 0;
    }