1 条题解

  • 0
    @ 2025-2-14 21:09:17

    C++ :

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <vector>
    #include <map>
    
    #define Maxn 61
    #define INF 4666662
    
    using namespace std;
    
    char a[Maxn][Maxn];	//原图
    int b[Maxn][Maxn];	//全息图
    int color=0,n,m;
    int ind[Maxn]={0},ond[Maxn]={0};	//记录入度 
    int total=0,ans=0;
    
    struct node{
    	bool vis[Maxn];
    	node() {memset(vis,0,sizeof(vis));}
    	bool operator < (const node a) const {
    		for(int i = 1;i <= n;i ++)
    		{
    			if(vis[i] != a.vis[i])
    			{
    				return vis[i] < a.vis[i];
    			}
    		}
    		return vis[n] < a.vis[n];
    	}
    } vis;
    
    map<node,int> Map;
    map<node,bool> Vis;
    vector<int> G[Maxn];	//存真图
    
    void Add(int y,int x)
    {
    	G[x].push_back(y);
    	ind[y] ++;
    	ond[y] ++;
    }
    
    void Build()		//建真图 
    {
    	for(int i = 1;i <= n;i ++)
    	{
    		for(int j = 1;j <= m;j ++)
    		{
    			if(b[i][j])
    			{
    				if(a[i][j] == '^')
    				{
    					for(int k = i - 1;k >= 1;k --)
    					{
    						if(a[k][j] == '#') break;	//拓展上面 
    						if(b[k][j])
    						{
    							Add(b[k][j],b[i][j]);
    						}
    					}
    				}
    				else if(a[i][j] == '>')
    				{
    					for(int k = j + 1;k <= m;k ++)
    					{
    						if(a[i][k] == '#') break;	//拓展右边 
    						if(b[i][k])
    						{
    							Add(b[i][k],b[i][j]);
    						}
    					}
    				}
    				else if(a[i][j] == '<')
    				{
    					for(int k = j - 1;k >= 1;k --)	//拓展左边 
    					{
    						if(a[i][k] == '#') break;
    						if(b[i][k])
    						{
    							Add(b[i][k],b[i][j]);
    						}
    					}
    				}
    				else if(a[i][j] == 'v')
    				{
    					for(int k = i + 1;k <= n;k ++)	//拓展下边 
    					{
    						if(a[k][j] == '#') break;
    						if(b[k][j])
    						{
    							Add(b[k][j],b[i][j]);
    						}
    					}
    				}
    			}
    		}
    	}
    }
    
    int q[Maxn*2]={0},en=0;		//建栈,进行拓扑排序 
    
    bool Solve()	//A_star 作为估价函数一 
    {
    	bool flag = false;
    	for(int i = 1;i <= color;i ++)
    	{
    		if(ind[i] == 0)
    		{
    			q[++en] = i;
    			ind[i] = 0x7fffffff;	//将入度为零的点入栈 
    			flag = true;
    		}
    	}
    	total ++;
    	while(en >= 0)
    	{
    		while(en >= 0)
    		{
    			for(int j = 0;j < G[q[en]].size();j ++)
    			{
    				ind[G[q[en]][j]] --;	//逐层拓展 
    			}
    			en --;
    		}
    		flag = false;
    		for(int i = 1;i <= color;i ++)	//拓展进栈
    		{
    			if(ind[i] == 0)
    			{
    				q[++en] = i;
    				ind[i] = 0x7fffffff;
    				flag = true;
    			}
    		}
    		if(flag) total ++;	//记录层数
    	}
    	for(int i = 1;i <= color;i ++)
    	{
    		if(ind[i] < 100000)	//若有的点未遍历到false 
    		{
    			return false;
    		}
    	}
    	return true;	//所有敌人已消灭 
    }
    
    void Dfs(int now)
    {
    	bool flag = false;
    	int last = ans;
    	if(now == color)
    	{
    		ans ++;
    		return;
    	}
    	for(int i = 1;i <= color;i ++)
    	{
    		if(!vis.vis[i] && ond[i] == 0)
    		{
    			for(int j = 0;j < G[i].size();j ++)
    			{
    				if(!vis.vis[G[i][j]])
    				{
    					ond[G[i][j]] --;
    				}
    			}
    			flag = true;
    			vis.vis[i] = true;
    			if(!Vis[vis]) Dfs(now + 1);
    			else ans += Map[vis];
    			vis.vis[i] = false;
    			for(int j = 0;j < G[i].size();j ++)
    			{
    				if(!vis.vis[G[i][j]])
    				{
    					ond[G[i][j]] ++;
    				}
    			}
    		}
    	}
    	Vis[vis] = true;
    	if(!flag) Map[vis] = 0;
    	else Map[vis] = ans - last;
    }
    
    void Init()
    {
    	cin >> n >> m;
    	for(int i = 1;i <= n;i ++)
    	{
    		for(int j = 1;j <= m;j ++)
    		{
    			cin >> a[i][j];
    			if(a[i][j] != '.' && a[i][j] != '#')	//投射敌人 
    			{
    				b[i][j] = ++color;
    			}
    		}
    	}
    }
    
    int main()
    {
    	Init();
    	Build();
    	if(Solve())
    	{
    		Dfs(0);
    		if(ans < 0) ans = INF;
    		cout << ans << endl;
    	}
    	else cout << "Impossible" << endl;
    	
    	return 0;
    }
    
    • 1

    信息

    ID
    660
    时间
    1000ms
    内存
    128MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者