3963 - B. 水管工
最近小仲迷上一个角水管工的游戏，游戏的大致规则是这样的，一块矩阵土地被分为M×N的单位正方形，每一个单位正方形要不都埋设一根水管或者种植了树木（种植树木的地方没有管道），水管将从坐标为（1,1）的左部边缘，延伸到坐标为（M，N）的右部边缘。水管只有两种，如下图所示：
每种管道将占据一个单位正方形土地，你可以旋转每个单元正方形上的管道，使其构成一个管道系统，即创造一条从（1,1）到（M，N）的连通管道。如下图
Input
每个测试案例的第一行有两个数，第1个数是M，第2个数是N，(N，M<25)，接着是M行数据，每一行有N个非负整数，每个整数表示地图中的每一小格的管道摆放方式，其中0表示树木，1~6分别表示管道的6中不同的摆放方式。
.png)
Output
如果从（1，1）能够有创建管道连通（M，N），则输出yes，否则输出，no way。
Examples
Input
5 4 5 3 5 3 1 5 3 0 2 3 5 1 6 1 1 5 1 5 5 4 2 2 1 2 1 1 2 2 1 1 1 1
Output
yes no way no way
Solution C++
#include <iostream> #include <string> #include <algorithm> #include <string.h> using namespace std; const int M = 20; const int N = 20; int maze[M][N]; int visited[M][N]; int m, n; bool dfs(int row, int col, int pre) { if (row == m && col == n + 1) return true; if (row <1 || row >m || col < 1 || col > n) return false; if (visited[row][col] == 1) return false; int cur = maze[row][col]; if (maze[row][col] == 0) return false; visited[row][col] = 1; if (cur <= 4) { if (pre == 1 || pre == 3) { if (dfs(row, col + 1, 2)) return true; if (dfs(row, col - 1, 4)) return true; } if (pre == 2 || pre == 4) { if (dfs(row - 1, col, 3)) return true; if (dfs(row + 1, col, 1)) return true; } } else { if (pre == 1) { if (dfs(row + 1, col, pre)) return true; } if (pre == 2) { if (dfs(row, col + 1, pre)) return true; } if (pre == 3) { if (dfs(row - 1, col, pre)) return true; } if (pre == 4) { if (dfs(row, col - 1, pre)) return true; } } visited[row][col] = 0; return false; } int main() { while (cin >> m >> n) { for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) cin >> maze[i][j]; } memset(visited, 0, sizeof(visited)); if (dfs(1, 1, 2)) cout << "yes" << endl; else cout << "no way" << endl; //cout << ret; } return 0; }