有的题用DFS超时，用BFS不超时，原因是？

可以把dfs和bfs的代码发链接呗 一般情况下，既可以用bfs又可以用dfs的题目，两个都不会被卡。 在没有代码的情况下，我觉得很可能dfs的时候发生了一些不可控的转移，导致时间复杂度增加？

#include<stdio.h> #include<stdlib.h> #include<iostream> #include<vector> #include<string> #include<sstream> #include<algorithm> #include<stack> #include<queue> #include<numeric> #include<cstring> #include<map> #include<set> #include<iostream> #include<cstdio> #include<algorithm> #include<vector> #include<map> #include<set> #include<stack> #include<list> #include<string> #include<cstdlib> #include<queue> #include<iomanip> #include<climits> #include<fstream> #include<unordered_set> #include<unordered_map> #include<functional> using namespace std; int min_cost = INT_MAX; int N, M; int beginx, beginy, endx, endy; void dfs(vector<int> &A, vector<int> &B, vector< vector<int> > &graph, int indexx, int indexy, int cost) { //cout << "in" << indexx << indexy << endl; if (indexx == endx && indexy == endy) { graph[endx][endy] = min(cost, graph[endx][endy]); return; } if (graph[indexx][indexy] == -1 || graph[indexx][indexy] < cost) { return; } graph[indexx][indexy] = cost; if (cost >= graph[endx][endy]) { return; } if (indexx - 1 >= 0) { //cout << "1locate:" << indexx << indexy << endl; if( cost +B[indexx-1] < graph[endx][endy] && cost + B[indexx-1] < graph[indexx-1][indexy] && graph[indexx-1][indexy] != -1) dfs(A, B, graph, indexx - 1, indexy, cost + B[indexx - 1]); } if (indexx + 1 < N) { //cout << "locate:" << indexx << indexy << endl; if( cost +B[indexx] < graph[endx][endy] && cost + B[indexx] < graph[indexx+1][indexy] && graph[indexx+1][indexy] != -1) dfs(A, B, graph, indexx + 1, indexy, cost + B[indexx]); } if (indexy - 1 >= 0) { //cout << "locate:" << indexx << indexy << endl; //cout << "3" << endl; if( cost +A[indexy -1] < graph[endx][endy] && cost + A[indexy-1] < graph[indexx][indexy-1] && graph[indexx][indexy-1] !=-1) dfs(A, B, graph, indexx, indexy - 1, cost + A[indexy - 1]); } if (indexy + 1 < M) { //cout << "locate:" << indexx << indexy << endl; //cout << "4" << endl; if( cost +A[indexy] < graph[endx][endy] && cost + A[indexy] < graph[indexx][indexy+1] && graph[indexx][indexy+1] != -1) dfs(A, B, graph, indexx, indexy + 1, cost + A[indexy]); } } typedef pair<int, int> P; int dx[4] = { -1,1, 0,0 }; int dy[4] = { 0, 0, 1, -1 }; int calc_dist(int x, int y, int k, vector<int> &A, vector<int> &B) { if (k == 0) return B[x - 1]; if (k == 1) return B[x]; if (k == 2) return A[y]; return A[y - 1]; }; void bfs(vector<int> &A, vector<int> &B, vector< vector<int> > &graph, int indexx, int indexy, int cost) { queue< pair<int, int> > que; que.push(P(indexx, indexy)); graph[indexx][indexy] = 0; while (!que.empty()) { P v = que.front(); que.pop(); for (int i = 0; i < 4; ++i) { int nx = v.first + dx[i]; int ny = v.second + dy[i]; //if (nx >= 0 && nx < N && ny >= 0 && ny < M && graph[nx][ny] != -1 &&) { if (!(nx >= 0 && nx < N && ny >= 0 && ny < M && graph[nx][ny] != -1) || graph[nx][ny] <= graph[v.first][v.second] + calc_dist(v.first, v.second, i, A, B)) continue; graph[nx][ny] = graph[v.first][v.second] + calc_dist(v.first, v.second, i, A, B); que.push(P(nx, ny)); } } } int main() { while (scanf("%d %d", &N, &M) != EOF) { min_cost = INT_MAX; vector<int>A(M - 1, 0), B(N - 1, 0); for (int i = 0; i < N - 1; ++i) { scanf("%d", &B[i]); } for (int i = 0; i < M - 1; ++i) { scanf("%d", &A[i]); } int K; scanf("%d", &K); vector< vector<int> > graph(N, vector<int>(M, INT_MAX)); for (int i = 0; i < K; ++i) { int x, y; scanf("%d %d", &x, &y); graph[x - 1][y - 1] = -1; } int Q; scanf("%d", &Q); while (Q--) { scanf("%d %d %d %d", &beginx, &beginy, &endx, &endy); //graph[beginx][beginy] = 0; vector< vector<int> > tmp = graph; beginx -= 1; beginy -= 1; endx -= 1; endy -= 1; //bfs2(A, B, tmp, beginx, beginy, 0); dfs(A, B, tmp, beginx, beginy, 0); /* for (int i = 0; i < N; ++i) { for (int j = 0; j < M; ++j) { cout << tmp[i][j] << "\t"; } cout << endl; } */ if (tmp[endx][endy] == INT_MAX) { printf("-1\n"); } else { printf("%d\n", tmp[endx][endy]); } } } return 0; } DFS 和 BFS ，谢谢帮忙 【 在 whn6325689 的大作中提到: 】 : 可以把dfs和bfs的代码发链接呗 : 一般情况下，既可以用bfs又可以用dfs的题目，两个都不会被卡。 : 在没有代码的情况下，我觉得很可能dfs的时候发生了一些不可控的转移，导致时间复杂度增加？

如果是这样的话，我觉得有没有可能是你dfs传参太多了，导致速度下降，你可以考虑用全局变量代替。 虽然工程之中据说不是很建议过多使用全局变量，但是在算法比赛中，可控的全局变量可以有效地优化一些常数 【 在 xiaoxiamii 的大作中提到: 】 : #include<stdio.h> : #include<stdlib.h> : #include<iostream> : ...................

A，B，graph 全设置为全局后，还是TLE。 【 在 whn6325689 的大作中提到: 】 : 如果是这样的话，我觉得有没有可能是你dfs传参太多了，导致速度下降，你可以考虑用全局变量代替。 : 虽然工程之中据说不是很建议过多使用全局变量，但是在算法比赛中，可控的全局变量可以有效地优化一些常数

也有可能是测试数据的原因，毕竟玄学……还有时倒着搜能过正着搜过不了~_~ 发自「贵邮」

呀！我发现你的代码写错了一个位置 if (indexy + 1 < M) { //cout << "locate:" << indexx << indexy << endl; //cout << "4" << endl; if( cost +A[indexy] < graph[endx][endy] && cost + A[indexy] < graph[indexx][indexy+1] && graph[indexx][indexy]+1 != -1) dfs(A, B, graph, indexx, indexy + 1, cost + A[indexy]); } 的graph[indexx][indexy]+1 != -1，应该是错了吧？

额 有点错， graph[indexx][indexy+1] != -1 一直在改优化。 【 在 whn6325689 的大作中提到: 】 : 呀！我发现你的代码写错了一个位置 : if (indexy + 1 < M) { : //cout << "locate:" << indexx << indexy << endl; : ...................

不影响TLE.. 【 在 whn6325689 的大作中提到: 】 : 呀！我发现你的代码写错了一个位置 : if (indexy + 1 < M) { : //cout << "locate:" << indexx << indexy << endl; : ...................

真是玄学 ╮(╯▽╰)╭，我是不懂了。 【 在 asv000 的大作中提到: 】 : 也有可能是测试数据的原因，毕竟玄学……还有时倒着搜能过正着搜过不了~_~ : 发自「贵邮」