题目描述给定一个由WWW条东西向街道和NNN条南北向街道组成的网格城市。街道交叉口有些是安全的有些是不安全的包含地下通道步行者避开。从城市公园位于西北角即(1,1)(1,1)(1,1)出发到东南角火车站(W,N)(W,N)(W,N)要求只能向东或向南移动即最短路径长度为WN−2WN-2WN−2个街区且必须避开所有不安全交叉口。计算满足条件的不同路径数。输入格式第一行为一个正整数表示测试用例个数随后有一个空行。每个测试用例第一行为两个整数WWW和NNN分别表示东西向和南北向街道数量。随后WWW行每行以该东西向街道的编号开头后跟零个或多个不安全交叉口的南北向街道编号。若某行只有街道编号则表示该街道上没有不安全交叉口。输入以空行分隔测试用例。输出格式对于每个测试用例输出一行包含一个整数表示从(1,1)(1,1)(1,1)到(W,N)(W,N)(W,N)的最短安全路径数。不同测试用例输出之间用一个空行分隔。样例输入1 4 5 1 2 2 3 3 5 4样例输出4题目分析网格中只能向右或向下移动因此路径长度为固定值(W−1)(N−1)(W-1) (N-1)(W−1)(N−1)。求从左上到右下避开某些格子的路径数是典型的动态规划问题。设dp[i][j]\textit{dp}[i][j]dp[i][j]为从(1,1)(1,1)(1,1)到(i,j)(i,j)(i,j)的安全路径数转移方程为dp[i][j]{0若 (i,j) 不安全dp[i−1][j]dp[i][j−1]否则 \textit{dp}[i][j] \begin{cases} 0 \text{若 } (i,j) \text{ 不安全} \\ \textit{dp}[i-1][j] \textit{dp}[i][j-1] \text{否则} \end{cases}dp[i][j]{0dp[i−1][j]dp[i][j−1]​若(i,j)不安全否则​其中边界条件dp[1][1]1\textit{dp}[1][1] 1dp[1][1]1若起点安全。最后答案即为dp[W][N]\textit{dp}[W][N]dp[W][N]。解题思路实现步骤确定如下步骤1\texttt{1}1. 读入测试用例个数忽略空行。步骤2\texttt{2}2. 对每个测试用例读入WWW和NNN初始化不安全标记数组blocked[W1][N1]\textit{blocked}[W1][N1]blocked[W1][N1]为000。步骤3\texttt{3}3. 循环读取WWW行每行包含一个街道编号和若干不安全交叉口的列号。对于每个列号ccc设置blocked[row][c]1\textit{blocked}[row][c] 1blocked[row][c]1。若某行只有编号则没有不安全交叉口。步骤4\texttt{4}4. 初始化dp\textit{dp}dp数组为000设置dp[1][1]1\textit{dp}[1][1] 1dp[1][1]1若起点安全。按行从上到下、列从左到右计算dp[i][j]\textit{dp}[i][j]dp[i][j]。若(i,j)(i,j)(i,j)不安全则dp[i][j]0\textit{dp}[i][j] 0dp[i][j]0否则dp[i][j]dp[i−1][j]dp[i][j−1]\textit{dp}[i][j] \textit{dp}[i-1][j] \textit{dp}[i][j-1]dp[i][j]dp[i−1][j]dp[i][j−1]注意边界条件i1i1i1或j1j1j1时仅从一侧转移。步骤5\texttt{5}5. 输出dp[W][N]\textit{dp}[W][N]dp[W][N]。结果可能较大使用646464位整数long long\texttt{long long}long long存储。代码实现// Walking on the Safe Side// UVa ID: 825// Verdict: Accepted// Submission Date: 2016-12-17// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcases0,W,N,blocked[110][110],number;longlongintways[110][110];string line;getline(cin,line);casesstoi(line);getline(cin,line);for(intc1;ccases;c){if(c1)cout\n;getline(cin,line);istringstreamiss(line);issWN;memset(blocked,0,sizeof(blocked));while(getline(cin,line),line.length()0){iss.clear();iss.str(line);vectorintnumbers;while(issnumber)numbers.push_back(number);for(inti1;inumbers.size();i)blocked[numbers.front()][numbers[i]]1;}memset(ways,0,sizeof(ways));ways[0][1]1;for(inti1;iW;i)for(intj1;jN;j)if(blocked[i][j])ways[i][j]0;elseways[i][j]ways[i-1][j]ways[i][j-1];coutways[W][N]\n;}return0;}总结本题通过动态规划求解网格中避开障碍物的最短路径数。由于移动方向受限只向下和向右路径数满足加法递推。输入格式需注意每行可能以空行结束使用getline和字符串流解析。起点(1,1)(1,1)(1,1)和终点(W,N)(W,N)(W,N)通常安全但代码中若起点被标记为不安全则dp[1][1]\textit{dp}[1][1]dp[1][1]会为000因为初始化为000且转移不会到达。为保险可显式设置dp[1][1]1\textit{dp}[1][1] 1dp[1][1]1若安全。该解法时间复杂度O(W×N)O(W \times N)O(W×N)空间O(W×N)O(W \times N)O(W×N)对于W,NW, NW,N不超过100100100的情况完全可行。