英文:
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.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论