英文:
same complexity code executes in Java but time limit exceeds in C++
问题
The C++ code you provided seems to be similar to the Java code for finding all possible paths of a knight on a chessboard. However, you mentioned that the C++ code encounters a time limit issue while the Java code runs fine. One possible reason for this discrepancy could be related to input and output handling.
In the C++ code, you are using cin for input and cout for output. Input and output operations in C++ can be relatively slower than in Java. To potentially improve the performance of your C++ code, you can try the following:
-
Optimize Input/Output: Use
std::ios::sync_with_stdio(false);at the beginning of your C++mainfunction to disable synchronization between C and C++ standard streams, which can speed up input and output operations. Here's how you can do it:int main() {std::ios::sync_with_stdio(false);int n; cin >> n;int r; cin >> r;int c; cin >> c;vector<vector<int>> path(n, vector<int>(n, 0));solve(r, c, path, 1, n);return 0;}
-
Use
printfandscanf: In C++, you can also useprintffor output andscanffor input, which may be faster thancinandcout. Here's an example:int main() {int n, r, c;scanf("%d %d %d", &n, &r, &c);vector<vector<int>> path(n, vector<int>(n, 0));solve(r, c, path, 1, n);return 0;}
These optimizations might help improve the performance of your C++ code and reduce the time limit issue. If the problem persists, consider profiling your code to identify specific bottlenecks that could be causing the performance difference between Java and C++.
英文:
The following is the code for finding all possible path of a knight on a chessboard of variable size
where the initial position is given.
The java code for this problem runs fine but for C++ The time limit exceeds.
JAVA CODE
import java.io.*;import java.util.*;public class Main {public static void main(String[] args) throws Exception {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int r = sc.nextInt();int c = sc.nextInt();int [][] path = new int[n][n];solve(r,c,path,1,n);}public static void solve(int r , int c , int[][] path , int move , int n) {if(r<0 || r>=n || c<0 || c>=n || path[r][c]>0)return;if(move == n*n){path[r][c] = n*n;display (path,n);path[r][c] = 0;return;}path[r][c] = move;solve(r-2,c+1,path,move+1,n);solve(r-1,c+2,path,move+1,n);solve(r+1,c+2,path,move+1,n);solve(r+2,c+1,path,move+1,n);solve(r+2,c-1,path,move+1,n);solve(r+1,c-2,path,move+1,n);solve(r-1,c-2,path,move+1,n);solve(r-2,c-1,path,move+1,n);path[r][c] = 0 ;}public static void display(int [][] path , int n){for(int i=0;i<n;i++){for(int j=0;j<n;j++){System.out.print(path[i][j]+" ");}System.out.print("\n");}System.out.print("\n");}}
C++ code
#include<bits/stdc++.h>using namespace std;void display( vector<vector<int>> path , int n){for(int i=0;i<n;i++){for(int j=0;j<n;j++){cout<<path[i][j]<<" ";}cout<<("\n");}cout<<("\n");}void solve(int r , int c ,vector<vector<int>> path , int move , int n) {if(r<0 || r>=n || c<0 || c>=n || path[r][c]>0)return;if(move == n*n){path[r][c] = n*n;display (path,n);path[r][c] = 0;return;}path[r][c] = move;solve(r-2,c+1,path,move+1,n);solve(r-1,c+2,path,move+1,n);solve(r+1,c+2,path,move+1,n);solve(r+2,c+1,path,move+1,n);solve(r+2,c-1,path,move+1,n);solve(r+1,c-2,path,move+1,n);solve(r-1,c-2,path,move+1,n);solve(r-2,c-1,path,move+1,n);path[r][c] = 0 ;}int main (){int n; cin>>n;int r; cin>>r;int c; cin>>c;vector<vector<int>> path(n,vector<int>(n,0));solve(r,c,path,1,n);return 0;}
please help me to sort out why is this so??
答案1
得分: 1
在你的Java代码中，数组没有被复制，而是传递了它的引用。
另一方面，在你的C++代码中，数组在每次函数调用时都被复制。
为了避免这种情况，你应该在函数参数中使用引用 vector<vector<int>>& path（添加 &）。
英文:
In your Java code, the array is not copied and its reference is passed.
On the other hand, in your C++ code, the array is copied on every function calls.
To avoid this, you should use reference vector<vector<int>>& path (add &) for your function arguments.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论