P7185 [CRCI2008-2009] CIJEVI题解
_xiaxii
·
·
题解
P7185 [CRCI2008-2009] CIJEVI
还没有题解，赶紧水一篇。
Wrote\space on\space 2022/11/29
## 题意理解
输入一张管道的图，求缺失的一块管道的信息。
这是一道模拟题，给出一种~~有趣~~繁琐的做法。题目给出了起点终点，且只有一块管道是缺失的。我们其实可以沿着整个管道走一遍。考虑到地图和管道的种类不是很多，可以采用枚举的方法。首先我们使用一个 `map` 来表示这个方向是否可走。定义一个函数 `f(int x,int y,int d)` 来走路径，其中 $x$ 与 $y$ 来表示当前的坐标，$d$ 表示方向。第一次调用 `f(x,y,d)` 函数我们通过第一个空格可以找到缺少的管道的坐标。然后再进行 $7$ 次的对管道类型的枚举，我们就可以开始走了。
首先在起点处找第一个管道，且只有一条，因为题目说明了**该计划将没有冗余构建块，即在添加丢失的块之后必须使用计划中的所有块**，否则管道的另一边会被堵死。如果检测到撞到管道壁或者当前在空格的位置，即无法继续往后走下去了，这种填法就是错误的。
我们定义向上为 $1$，向右为 $2$，向下为 $3$，向左为 $4$。方向的变换之间有一对一的关系，变换稍微有点复杂，要注意不要写错。
- 若当前管道为 `+`，则方向不改变。
- 若当前管道为 `-`，则方向不改变。
- 若当前管道为 `|`，则方向不改变。
- 若当前管道为 `1`，则方向 $1$ 变为 $2$，$4$ 变为 $3$。
- 若当前管道为 `2`，则方向 $3$ 变为 $2$，$4$ 变为 $1$。
- 若当前管道为 `3`，则方向 $3$ 变为 $4$，$2$ 变为 $1$。
- 若当前管道为 `4`，则方向 $2$ 变为 $3$，$1$ 变为 $4$。
枚举要把 `+` 的情况放在最后，因为这个管道会影响到 `-` 和 `|` 的情况。
看似已经没有问题了，交上去，[错了两个点](https://www.luogu.com.cn/record/96034428)。
仔细思考，就会发现一个问题，比如说如下的结构：
$$\begin{matrix}
. &.&1&-&4\\
. & .&|&.&|\\
M & -&.&-&3\\
.&.&|&.&.\\
.&.&Z&.&.
\end{matrix}$$
根据题目所说的**该计划将没有冗余构建块，即在添加丢失的块之后必须使用计划中的所有块**，我们很容易看出来在 $(3,3)$ 的位置应该填 `+`，**然而程序填了 `4`**。
这个问题很好解决，用一个 `book` 数组标记每个管道是否用过就行了。
## Hack
~~时隔一年的Hack。~~
考虑这样的数据：
```
1 3
M.Z
```
运行之后发现什么也没输出。仔细看看代码会发现，如果入口处没有任何管道，则 `fixx` 和 `fixy` 中都不会有值。解决办法是直接在入口周围的空地上枚举管道直到成功。
## 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
int r,c;
int sx,sy,fx,fy,dir,fixx,fixy,block=6;
int book[50][50];//记录是否走过
char e[30][30];
bool flag=true, hack = false;
//用几个map来标记当前是否可走
map<char,int> _left;
map<char,int> up;
map<char,int> _right;
map<char,int> down;
int nt[4][2]={{-1,0},{0,1},{1,0},{0,-1}};//位置的变化量
char bl[8]={'+','-','|','1','2','3','4'};//记录每种管道
void check()//找到第一步的方向
{
if(up[e[sx-1][sy]])
{
dir=1;
}
if(_right[e[sx][sy+1]])
{
dir=2;
}
if(down[e[sx+1][sy]])
{
dir=3;
}
if(_left[e[sx][sy-1]])
{
dir=4;
}
}
bool k(int x,int y,int d)//判断这一步是否可走
{
x+=nt[d-1][0];
y+=nt[d-1][1];
if(d==1)
{
return up[e[x][y]];
}
if(d==2)
{
return _right[e[x][y]];
}
if(d==3)
{
return down[e[x][y]];
}
if(d==4)
{
return _left[e[x][y]];
}
}
void f(int x,int y,int d)
{
book[x][y]=1;
//对方向的更新
int p=d;
if(e[x][y]==bl[3])
{
p=d==1?2:3;
}
if(e[x][y]==bl[4])
{
p=d==3?2:1;
}
if(e[x][y]==bl[5])
{
p=d==3?4:1;
}
if(e[x][y]==bl[6])
{
p=d==1?4:3;
}
//模拟每种管道的走法
if(e[x][y]==bl[0]&&((d==1&&k(x,y,d))||(d==2&&k(x,y,d))||(d==3&&k(x,y,d))||(d==4&&k(x,y,d))))
{
f(x+nt[d-1][0],y+nt[d-1][1],d);
}
else if(e[x][y]==bl[1]&&((d==2&&k(x,y,d))||(d==4&&k(x,y,d))))
{
f(x,y+nt[d-1][1],d);
}
else if(e[x][y]==bl[2]&&((d==1&&k(x,y,d))||(d==3&&k(x,y,d))))
{
f(x+nt[d-1][0],y,d);
}
else if(e[x][y]==bl[3]&&((d==1&&k(x,y,2))||(d==4&&k(x,y,3))))
{
p=d==1?2:3;
f(x+nt[p-1][0],y+nt[p-1][1],p);
}
else if(e[x][y]==bl[4]&&((d==3&&k(x,y,2))||(d==4&&k(x,y,1))))
{
p=d==3?2:1;
f(x+nt[p-1][0],y+nt[p-1][1],d==3?2:1);
}
else if(e[x][y]==bl[5]&&((d==2&&k(x,y,1))||(d==3&&k(x,y,4))))
{
p=d==3?4:1;
f(x+nt[p-1][0],y+nt[p-1][1],d==3?4:1);
}
else if(e[x][y]==bl[6]&&((d==2&&k(x,y,3))||(d==1&&k(x,y,4))))
{
p=d==1?4:3;
f(x+nt[p-1][0],y+nt[p-1][1],d==1?4:3);
}
else if(x+nt[p-1][0]==fx&&y+nt[p-1][1]==fy)//如果走到了终点
{
bool flag2=true;
for(int i=1;i<=r;i++)
{
for(int j=1;j<=c;j++)
{
if(e[i][j]!='.'&&e[i][j]!='M'&&e[i][j]!='Z')//如果是管道
{
if(!book[i][j])//如果没走过
flag2=false;
}
}
}
if(flag2)
{
if(hack) --block;
cout<<fixx<<" "<<fixy<<" "<<bl[block];//满足所有的要求就是答案了，可以直接退出
exit(0);
}
}
else if(flag)//第一次进入
{
flag=false;
fixx=x+nt[p-1][0],fixy=y+nt[p-1][1];
}
}
int main()
{
cin>>r>>c;
for(int i=1;i<=r;i++)
{
for(int j=1;j<=c;j++)
{
cin>>e[i][j];
if(e[i][j]=='M')
{
sx=i;
sy=j;
}
if(e[i][j]=='Z')
{
fx=i;
fy=j;
}
}
}
//定义哪些可以走
_left['+']=1;
_left['-']=1;
_left['1']=1;
_left['2']=1;
up['+']=1;
up['|']=1;
up['1']=1;
up['4']=1;
_right['+']=1;
_right['-']=1;
_right['3']=1;
_right['4']=1;
down['+']=1;
down['|']=1;
down['2']=1;
down['3']=1;
check();
f(sx+nt[dir-1][0],sy+nt[dir-1][1],dir);//第一遍调用找到缺少的坐标
if(fixx == sx && fixy == sy){ //新增的Hack内容
hack = true;
for(; block >= 0; block--){
for(int i=0; i<4; i++){
int x = sx + nt[i][0];
int y = sy + nt[i][1];
if(e[x][y] == '.'){
e[x][y] = bl[max(0, block)];
fixx = x, fixy = y;
check();
f(sx+nt[dir-1][0],sy+nt[dir-1][1],dir);
e[x][y] = '.';
}
}
}
}
while(block>=0)
{
memset(book, 0, sizeof(book));//每次枚举要重置book数组
if(!flag)e[fixx][fixy]=bl[max(0,block)];//将枚举的管道拼接到地图中
f(sx+nt[dir-1][0],sy+nt[dir-1][1],dir);
block--;//记得从后向前枚举，前文有提及
}
}
```
实测[满分](https://www.luogu.com.cn/record/96036189)。
本[蒟蒻](https://www.luogu.com.cn/user/728002)的第六篇题解。