1 条题解
-
0
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
- 上传者