商城网站怎么做优化,怀集网站建设,公司网站开发费怎么入账,足彩网站建设1.优解思路#xff1a;
秒啊#xff1a;如果这条路可以走通#xff0c;则这条路上所有点都可以走通#xff0c;反之若不可以#xff0c;则都不可以。
因为比如一个点走了#xff0c;没走通#xff0c;这条路上的点都出不去#xff0c;假如有别的点走路走到这条死路上…1.优解思路
秒啊如果这条路可以走通则这条路上所有点都可以走通反之若不可以则都不可以。
因为比如一个点走了没走通这条路上的点都出不去假如有别的点走路走到这条死路上的任意一点路线交叉岂不是肯定出不去。
所以用一个solve数组记录当走下一步时不用return dfs直接判断ifdfs()如果可以 就标记solve可以并且返回true。
2.这里我一开始就把solve数组清0了有保障些。
3.复杂度分析上一个解答是假设n行n列对于一个点dfs一次最多把迷宫每个点都走一遍就是On^2次如果每个点都要像刚刚那个点一样那么累那么就是On^4
这个优化后的方法对于一个点如果dfs一次若把迷宫都走遍那么迷宫每个solve都标注好了所以就是On^2
#includeiostream
#includecstring
using namespace std;int ans 0;
char mp[12][12];
bool vis[12][12];
int solve[12][12];
bool dfs(int i, int j) {if (vis[i][j]) return false;if (i 1 || j 1 || i10 || j10) {return true;}if (solve[i][j] 1) return true;if (solve[i][j] 2) return false;//真的得按编译器来这个只能false不能Falsevis[i][j] 1;if (mp[i][j] U) {if (dfs(i - 1, j)) {solve[i][j] 1;return 1;}else {solve[i][j] 2;return 0;}}if (mp[i][j] D) {if (dfs(i1, j )) {solve[i][j] 1;return 1;}else {solve[i][j] 2;return 0;}}if (mp[i][j] L) {if (dfs(i, j - 1)) {solve[i][j] 1;return 1;}else {solve[i][j] 2;return 0;}}if (mp[i][j] R) {if (dfs(i , j1)) {solve[i][j] 1;return 1;}else {solve[i][j] 2;return 0;}}
}
int main() {for (int i 1; i 10; i) {for (int j 1; j 10; j) {cin mp[i][j];}}memset(solve, 0, sizeof(solve));for (int i 1; i 10; i) {for (int j 1; j 10; j) {memset(vis, 0, sizeof(vis));if (dfs(i, j))ans;}}cout ans;
}
