输油管道 (Standard IO)
Time Limits: 1000 ms Memory Limits: 65536 KB Detailed Limits
Time to Submit: 01:58:44
Description
请你帮忙设计一个从城市M到城市Z的输油管道，现在已经把整个区域划分为R行C列，每个单元格可能是空的也可能是以下7种基本管道之一：
油从城市M流向Z，‘+’型管道比较特殊，因为石油必须在两个方向（垂直和水平）上传输，如下图所示：
现在恐怖分子弄到了输油管道的设计图，并把其中一个单元格中的管道偷走了，请你帮忙找到偷走的管道的位置以及形状。
Input
第一行包含两个整数R和C（1<=R,C<=25）。
接下来R行每行C个字符描述被偷之后的形状，字符分为以下三种：
(1)‘.’表示空；
(2)字符‘|’（ASCII为124）、‘-’、‘+’、‘1’、‘2’、‘3’、‘4’描述管道的形状；
(3)‘M’和‘Z’表示城市，两个都是只出现一次。
输入保证石油的流向是唯一的，只有一个管道跟M和Z相连，除此此外，保证没有多余的管道，也就是说所有的管道在加进被偷的管道后一定都会被用上。
输入保证有解而且是唯一的。
Output
输出被偷走的管道的行号和列号以及管道的类型。
Sample Input
输入1：
3 7
.......
.M-.-Z.
.......
输入2：
3 5
..1-M
1-+..
Z.23.
输入3：
6 10
Z.1----4..
|.|....|..
|..14..M..
2-+++4....
..2323....
..........
Sample Output
输出1：
2 4 -
输出2：
2 4 4
输出3：
3 3 |
Data Constraint
一、错误但是能过的暴力
在考场上，我观察到数据范围很小（就是不会打算暴力），然后就考虑了沿着管道进行搜索。至于填补的管道，我直接枚举了，时间复杂度（n^4 * k） = 2434375，在1e6左右还是能过的。
但是没有考虑到‘+’的情况所以死了。
之后考虑‘+’，由于使用所有管道（早看到这个要素就有更优算法了），所以只要空着的点上下左右都有管道，这个点一定是‘+’。
就这样卡过了数据
（考场上写两百行的判断我真的是。。。）
#include<bits/stdc++.h> using namespace std; /*---------------------------- | 7 - 5 + 6 1 2 3 4 Z,M;11,12; -----------------------------*/ const int MAXN = 29; int charget() { char c = 0; while((c = getchar()) != '|' && c != '.' && c != '-' && c != '+' && c != '1' && c!= '2' && c != '3' && c != '4' && c!= 'Z' && c != 'M'); if(c == '|') return 7; if(c == '-') return 5; if(c == '+') return 6; if(c == '.') return 0; if(c == 'Z') return 11; if(c == 'M') return 12; else return c - '0'; } int map[MAXN][MAXN]; int mp[MAXN][MAXN]; int ou[MAXN][MAXN];//1 走了横向 2 走了纵向 3 都走了 bool v[MAXN][MAXN]; int n,m,Mx,My,Zx,Zy; char out[10] = {0,'1','2','3','4','-','+','|'}; void testmap() { for(register int i = 1; i <= n; ++i) { for(register int j = 1; j <= m; ++j) { cerr<<::map[i][j]<<' '; } cerr<<endl; } } void testmp() { for(register int i = 1; i <= n; ++i) { for(register int j = 1; j <= m; ++j) { cerr<<::v[i][j]<<' '; } cerr<<endl; } } void dfs(int x,int y,int nowx,int nowy)//nowx nowy记录上一个点的位置 { if(v[x][y] && ::map[x][y] != 6 && mp[x][y] != 6) return; // cerr<<x<<" "<<y<<" "<<nowx<<""<<nowy<<endl; v[x][y] = 1; if(::map[x][y] == 1 || mp[x][y] == 1) { if(nowx == x && nowy == y + 1) dfs(x+1,y,x,y); if(nowx == x + 1 && nowy == y ) dfs(x,y+1,x,y); } if(::map[x][y] == 2 || mp[x][y] == 2) { if(nowx == x - 1 && nowy == y) dfs(x,y+1,x,y); if(nowx == x && nowy == y + 1) dfs(x-1,y,x,y); } if(::map[x][y] == 3 || mp[x][y] == 3) { if(nowx == x && nowy == y - 1) dfs(x-1,y,x,y); if(nowx == x - 1 && nowy == y) dfs(x,y-1,x,y); } if(::map[x][y] == 4 || mp[x][y] == 4) { if(nowx == x && nowy == y - 1) dfs(x+1,y,x,y); if(nowx == x + 1 && nowy == y) dfs(x,y-1,x,y); } if(::map[x][y] == 5 || mp[x][y] == 5) { if(nowx == x && nowy == y + 1) dfs(x,y-1,x,y); if(nowx == x && nowy == y - 1) dfs(x,y+1,x,y); } if(::map[x][y] == 7 || mp[x][y] == 7) { if(nowx == x - 1 && nowy == y) dfs(x+1,y,x,y); if(nowx == x + 1 && nowy == y) dfs(x-1,y,x,y); } if(::map[x][y] == 6 || mp[x][y] == 6) { if(ou[x][y] == 3) { return; } if(ou[x][y] == 0) { if(nowy == y) { ou[x][y] = 2; dfs(x+1,y,x,y); dfs(x-1,y,x,y); } if(nowx == x) { ou[x][y] = 1; dfs(x,y+1,x,y); dfs(x,y-1,x,y); } } if(ou[x][y] == 1) { if(nowx == x) return; if(nowy == y) { ou[x][y] = 3; dfs(x+1,y,x,y); dfs(x-1,y,x,y); } } if(ou[x][y] == 2) { if(nowy == y) { return; } if(nowx == x) { ou[x][y] = 3; dfs(x,y+1,x,y); dfs(x,y-1,x,y); } } } if(::map[x][y] == 12) { if(::map[x+1][y]) if(::map[x+1][y] == 7 || ::map[x+1][y] == 6 || ::map[x+1][y] == 2 || ::map[x+1][y] == 3) dfs(x+1,y,x,y); if(::map[x-1][y]) if(::map[x-1][y] == 7 || ::map[x-1][y] == 6 || ::map[x-1][y] == 1 || ::map[x-1][y] == 4) dfs(x-1,y,x,y); if(::map[x][y+1]) if(::map[x][y+1] == 5 || ::map[x][y+1] == 6 || ::map[x][y+1] == 3 || ::map[x][y+1] == 4) dfs(x,y+1,x,y); if(::map[x][y-1]) if(::map[x][y-1] == 5 || ::map[x][y-1] == 6 || ::map[x][y-1] == 1 || ::map[x][y-1] == 2) dfs(x,y-1,x,y); } if(::map[x][y] == 11) { v[x][y] == 1; return; } } int main() { #ifdef lky233 freopen("testdata.in","r",stdin); freopen("testdata.out","w",stdout); #endif cin>>n>>m; for(register int i = 1; i <= n; ++i) { for(register int j = 1; j <= m; ++j) { ::map[i][j] = charget(); if(::map[i][j] == 12) { Mx = i,My = j; } if(::map[i][j] == 11) { Zx = i,Zy = j; } } } // testmap(); // cerr<<"data::"<<Mx<<" "<<My<<endl; for(register int i = 1; i <= n; ++i) { for(register int j = 1;j <= m; ++j) { if(::map[i][j]) continue; for(register int k = 1; k <= 7; ++k) { if(k == 6) continue; memset(v,0,sizeof(v)); memset(ou,0,sizeof(ou)); mp[i][j] = k; // cerr<<i<<" "<<j<<" "<<out[k]<<"::"<<endl; dfs(Mx,My,0,0); if(v[Zx][Zy]) { // cerr<<k<<endl; if(::map[i-1][j] && ::map[i+1][j] && ::map[i][j-1] && ::map[i][j+1]) k = 6; cout<<i<<' '<<j<<' '<<out[k]<<endl; return 0; } } } } #ifdef lky233 testmap(); #endif }
二、大佬的std
由于使用所有管道，所以直接判断是否所有管道被使用，如果是的话就可以了
三、官方题解
PIPE
First write four auxiliary functions left(r,c), right(r,c), up(r,c) and down(r,c) telling us if gas can flow in
each direction from empty cell(r,c). For example, the function left(r,c) can look like this:
return true if Map(r,s−1) = '+' or Map(r,s−1) = '-' or Map(r,s−1) = '1' or Map(r,s−1) = '2'
The task can be solved in one pass through the map. For every empty cell(r, c) we run the following
checks:
if left(r,c) and right(r,c) and up(r,c) and down(r,c) then output r c '+'
else if left(r,c) and right(r,c) then output r c '-'
else if up(r,c) and down(r,c) then output r c '|'
else if right(r,c) and down(r,c) then output r c '1'
else if right(r,c) and up(r,c) then output r c '2'
else if left(r,c) and up(r,c) then output r c '3'
else if left(r,c) and down(r,c) then output r c '4'