同样复杂度的代码在Java中执行,但在C++中超过了时间限制。

huangapple go评论65阅读模式
英文:

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:

  1. Optimize Input/Output: Use std::ios::sync_with_stdio(false); at the beginning of your C++ main function 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;
    }
    
  2. Use printf and scanf: In C++, you can also use printf for output and scanf for input, which may be faster than cin and cout. 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&lt;0 || r&gt;=n || c&lt;0 || c&gt;=n || path[r][c]&gt;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&lt;n;i++)
    {
        for(int j=0;j&lt;n;j++)
        {
            System.out.print(path[i][j]+&quot; &quot;);
        }
        
        System.out.print(&quot;\n&quot;);
    }
    
    System.out.print(&quot;\n&quot;);
    
    }
    
}

C++ code

#include&lt;bits/stdc++.h&gt;
using namespace std;

    
 void display( vector&lt;vector&lt;int&gt;&gt; path , int n)
    {
        
     for(int i=0;i&lt;n;i++)
    {
        for(int j=0;j&lt;n;j++)
        {
            cout&lt;&lt;path[i][j]&lt;&lt;&quot; &quot;;
        }
        
        cout&lt;&lt;(&quot;\n&quot;);
    }
    
        cout&lt;&lt;(&quot;\n&quot;);
    
    }



    void solve(int r , int c ,vector&lt;vector&lt;int&gt;&gt; path , int move , int n) {
        
        if(r&lt;0 || r&gt;=n || c&lt;0 || c&gt;=n || path[r][c]&gt;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&gt;&gt;n;
        int r;  cin&gt;&gt;r;
        int c;  cin&gt;&gt;c;
        
        vector&lt;vector&lt;int&gt;&gt; path(n,vector&lt;int&gt;(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&lt;vector&lt;int&gt;&gt;&amp; path (add &amp;) for your function arguments.

huangapple
  • 本文由 发表于 2020年8月1日 15:10:16
  • 转载请务必保留本文链接:https://go.coder-hub.com/63202701.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定