目前做公司网站有没有用,大同建设局网站,网络推广免费平台,个人网站创意小N最近喜欢玩一款塔防游戏。
题目描述
这款游戏的棋盘是一个 nm 的网格#xff0c;每个格子上会有以下类型物件#xff1a;
A 型炮台#xff1a;会向上下两个方向同时发射激光#xff0c;符号为 |;B 型炮台#xff1a;会向左右两个方向同时发射激光#xff0c;符号为…小N最近喜欢玩一款塔防游戏。
题目描述
这款游戏的棋盘是一个 n×m 的网格每个格子上会有以下类型物件
A 型炮台会向上下两个方向同时发射激光符号为 |;B 型炮台会向左右两个方向同时发射激光符号为 -;空地激光穿过该物件会保持方向前进符号为 .;障碍激光到达该物件会消失符号为 #;正反射镜激光到达该物件后会依物理定律改变方向但仍继续前进符号为 \;副反射镜激光到达该物件后会依物理定律改变方向但仍继续前进符号为 /;
注意激光之间可以互相穿过但如果激光射出网格边界也会消失。 小 N 是一个强迫症玩家他想让每一处空地都会被至少一束激光打到但不能让激光攻击到自己的炮台以致损坏。 小 N 可以将任意多的 A 型炮台改造成 B 型炮台也可以把任意多的 B 型炮台改造成 A 型炮台。 你可以告诉他能否通过这些改造实现他的目标吗?
输入格式
第一行一个正整数 T表示数据组数。 每组数据第一行有两个正整数 n,m。 接下来 n 行每行一个长度为 m 的字符串表示棋盘。
输出格式
对于每组数据若无解则输出一行 IMPOSSIBLE否则输出一行 POSSIBLE再输出改造后的棋盘。 如果有多组解输出任意一个即可。 思路
首先 n,m≤50暴力枚举每个炮台的朝向是不可取的但可以分别计算每个炮台每种朝向能打到的格子。不难想到能打到自己炮台的炮台朝向一定是不可取的。
题目又说道要求每一处空地都会被至少一束激光打到那我们需要看每一处空地可能被哪些炮台的哪些朝向打到。
接下来是题目的核心每一处空地最多可能被哪些炮台的哪些可取的朝向打到呢 首先空地不会被两束同向的激光打到因为若可能它们必有重合的一段路径然而其中一束激光会被路径上的炮台或反射镜所影响。
举个例子
-.\.
....
-.\.
....此图中对于空地 (4,3)若上方除 (3,1) 的激光打来一定会碰到反射镜而改变路径。
其次空地也不会被两束反向的激光打到因为光路可逆若可能一束激光能打到空地则一定能沿着反向打到该空地的激光的逆光路打到另一个炮台。
还是通过举例说明
-..\
....
.-./
此图中两束激光均能打到 (2,4) 的空地且方向相反不难发现它们必能互相打到。
综上所述再根据抽屉原理每个空地最多可能被两个炮台的可取的朝向打到。 又因为至少被一束激光打到。所以每个空地均可被看作 i 炮台为横/竖向 或 j 炮台为横/竖向 的约束条件。 这里就能看出是 2-SAT 问题了根据前文所述用 2-SAT 模板的处理方法即可。
代码细节
思路是简明且重要的并且代码细节难度也不容小觑 毕竟是黑题
认为自己的代码实现思路是清晰且完备的下面进行展示。
遍历激光的路径使用 dfs除了建立方向数组再建立两个数组 lf[],rf[] 代表每种激光方向经过副/主反射镜后改变成的方向这样能简便地处理反射的问题。
const int dx[]{0,-1,0,1},dy[]{-1,0,1,0},lf[]{3,2,1,0},rf[]{1,0,3,2};
...
bool dfs(int x,int y,int dir){int xxxdx[dir],yyydy[dir];if(mp[xx][yy]#||xx1||xxn||yy1||yym)return 1;if(mp[xx][yy]/)return dfs(xx,yy,lf[dir]);if(mp[xx][yy]\\)return dfs(xx,yy,rf[dir]);if(mp[xx][yy].)return dfs(xx,yy,dir);return 0;
}对于每个朝向先 dfs 一次判断是否能打到其他炮台能则说明朝向不合法建一条选该朝向指向选另外朝向的边体现选该朝向就能推出矛盾。否则朝向合法再进行一次 dfs 寻找能打到的空地。这里用 i 表示横向用 itcnt 表示竖向。 for(int i1;itcnt;i){if(!dfs(towx[i],towy[i],0)||!dfs(towx[i],towy[i],2))add(i,itcnt);else{dfs2(i,towx[i],towy[i],0);dfs2(i,towx[i],towy[i],2);}if(!dfs(towx[i],towy[i],1)||!dfs(towx[i],towy[i],3))add(itcnt,i);else{dfs2(itcnt,towx[i],towy[i],1);dfs2(itcnt,towx[i],towy[i],3);}}接下来遍历每处空地建边注意分类讨论 若空地不能被任何激光打到直接无解。 若空地只能被一个炮台的朝向打到建一条不选该朝向指向选该朝向的边体现该朝向不得不选。 若空地能被两个炮台的朝向打到就是常规的 2-SAT分别建 ¬i→j 和 ¬j→i 的边。
这里定义了一个函数 opp 表示相反朝向对应的编号。 for(int i1;in;i){for(int j1;jm;j){if(mp[i][j].){int szS[i][j].size();if(sz0)add(1,tcnt1),add(tcnt1,1);if(sz1)add(opp(S[i][j][0]),S[i][j][0]);if(sz2){if(opp(S[i][j][0])!S[i][j][1])add(opp(S[i][j][0]),S[i][j][1]),add(opp(S[i][j][1]),S[i][j][0]);}}}}至此本题的所有代码难点都过去了接下来正常地跑 Tarjan通过强连通分量编号确定每个炮台的朝向即可 代码
#includecstdio
#includecstring
#includealgorithm
#includeiostream
#includevector
#define N 5010
#define M N1
using namespace std;
int T,n,m;
int low[N],dfn[N],scc[N],num,cnt,towx[N],towy[N],tcnt,flag;
int h[N],nxt[M],ver[M],tot,st[N],top;
const int dx[]{0,-1,0,1},dy[]{-1,0,1,0},lf[]{3,2,1,0},rf[]{1,0,3,2};
char mp[55][55];
vectorintS[55][55];
void init(){numcnttcnttop0,tot-1,flag1;memset(h,-1,sizeof(h)); memset(dfn,0,sizeof(dfn));memset(scc,0,sizeof(scc));for(int i1;in;i){for(int j1;jm;j)S[i][j].clear();}
}
void add(int x,int y){ver[tot]y;nxt[tot]h[x];h[x]tot;
}
int opp(int x){return xtcnt?xtcnt:x-tcnt;
}
bool dfs(int x,int y,int dir){int xxxdx[dir],yyydy[dir];if(mp[xx][yy]#||xx1||xxn||yy1||yym)return 1;if(mp[xx][yy]/)return dfs(xx,yy,lf[dir]);if(mp[xx][yy]\\)return dfs(xx,yy,rf[dir]);if(mp[xx][yy].)return dfs(xx,yy,dir);return 0;
}
void dfs2(int id,int x,int y,int dir){int xxxdx[dir],yyydy[dir];if(mp[xx][yy]#||xx1||xxn||yy1||yym)return ;if(mp[xx][yy]/)dfs2(id,xx,yy,lf[dir]);if(mp[xx][yy]\\)dfs2(id,xx,yy,rf[dir]);if(mp[xx][yy].)S[xx][yy].push_back(id),dfs2(id,xx,yy,dir);
}
void tarjan(int u){st[top]u;low[u]dfn[u]num;for(int ih[u];~i;inxt[i]){int vver[i];if(!dfn[v]){tarjan(v);low[u]min(low[v],low[u]);}else if(!scc[v])low[u]min(dfn[v],low[u]);}if(low[u]dfn[u]){cnt;while(1){int vst[top--];scc[v]cnt;if(vu)break;}}
}
int main(){scanf(%d,T);while(T--){scanf(%d%d,n,m);init();for(int i1;in;i){scanf(%s,mp[i]1);for(int j1;jm;j){if(mp[i][j]-||mp[i][j]|)towx[tcnt]i,towy[tcnt]j;}}for(int i1;itcnt;i){if(!dfs(towx[i],towy[i],0)||!dfs(towx[i],towy[i],2))add(i,itcnt);else{dfs2(i,towx[i],towy[i],0);dfs2(i,towx[i],towy[i],2);}if(!dfs(towx[i],towy[i],1)||!dfs(towx[i],towy[i],3))add(itcnt,i);else{dfs2(itcnt,towx[i],towy[i],1);dfs2(itcnt,towx[i],towy[i],3);}}for(int i1;in;i){for(int j1;jm;j){if(mp[i][j].){int szS[i][j].size();if(sz0)add(1,tcnt1),add(tcnt1,1);if(sz1)add(opp(S[i][j][0]),S[i][j][0]);if(sz2){if(opp(S[i][j][0])!S[i][j][1])add(opp(S[i][j][0]),S[i][j][1]),add(opp(S[i][j][1]),S[i][j][0]);}}}}for(int i1;i2*tcnt;i){if(!dfn[i])tarjan(i);}for(int i1;itcnt;i){if(scc[i]scc[itcnt]){printf(IMPOSSIBLE\n);flag0;break;}}if(flag){printf(POSSIBLE\n);for(int i1;itcnt;i){if(scc[i]scc[itcnt])mp[towx[i]][towy[i]]|;else mp[towx[i]][towy[i]]-;}for(int i1;in;i){printf(%s\n,mp[i]1);}}}return 0;
}
