tag:blogger.com,1999:blog-3418265334198879901.post5366198684691962889..comments2023-06-10T14:12:41.433+05:30Comments on Coders Stop: Euler problem : Finding the minimum sumAviralhttp://www.blogger.com/profile/11920144614598355124noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-3418265334198879901.post-8187998242373671542012-08-23T18:47:47.196+05:302012-08-23T18:47:47.196+05:30Below is my solution. It starts from Position(4,4)...Below is my solution. It starts from Position(4,4) and will back track till it reaches Position(0,0). This will also print the "Path" backwards.<br /><br />private static int minSumVariation(int[][] grid) {<br /> if (grid == null) {<br /> throw new NullPointerException();<br /> }<br /> int i = 4;<br /> int j = 4;<br /> int minSum = grid[i][j];<br /> Set visitedNodes = new HashSet();<br /> visitedNodes.add("" + i + j);<br /> StringBuilder route = new StringBuilder();<br /> route.append("" + minSum);<br /> while (true) {<br /> if (i - 1 < 0 && j - 1 < 0) {<br /> break;<br /> }<br /><br /> int min = 0;<br /> int iNext = 0;<br /> int jNext = 0;<br /><br /> if (j - 1 >= 0) {<br /> if (!visitedNodes.contains("" + i + (j - 1))) {<br /> min = grid[i][j - 1];<br /> iNext = i;<br /> jNext = j - 1;<br /> }<br /> }<br /> if (i - 1 >= 0) {<br /> if (!visitedNodes.contains("" + (i - 1) + j)) {<br /> if (min == 0) {<br /> min = grid[i - 1][j];<br /> iNext = i - 1;<br /> jNext = j;<br /> } else if (min > grid[i - 1][j]) {<br /> min = grid[i - 1][j];<br /> iNext = i - 1;<br /> jNext = j;<br /> }<br /> }<br /> }<br /> if (i + 1 < 5) {<br /> if (!visitedNodes.contains("" + (i + 1) + j)) {<br /> if (min == 0) {<br /> min = grid[i + 1][j];<br /> iNext = i + 1;<br /> jNext = j;<br /> } else if (min > grid[i + 1][j]) {<br /> min = grid[i + 1][j];<br /> iNext = i + 1;<br /> jNext = j;<br /> }<br /> }<br /> }<br /> if (j + 1 < 5) {<br /> if (!visitedNodes.contains("" + i + (j + 1))) {<br /> if (min == 0) {<br /> min = grid[i][j + 1];<br /> iNext = i;<br /> jNext = j + 1;<br /> } else if (min > grid[i][j + 1]) {<br /> min = grid[i][j + 1];<br /> iNext = i;<br /> jNext = j + 1;<br /> }<br /> }<br /> }<br /> route.append(" - " + min);<br /> minSum += min;<br /> i = iNext;<br /> j = jNext;<br /> visitedNodes.add("" + i + j);<br /> }<br /> <br /> System.out.println("route = " + route.toString());<br /> <br /> return minSum;<br /> }Debojit Saikiahttps://www.blogger.com/profile/18302009873923271496noreply@blogger.comtag:blogger.com,1999:blog-3418265334198879901.post-29712094055974599052012-08-23T18:22:49.860+05:302012-08-23T18:22:49.860+05:30This comment has been removed by the author.Debojit Saikiahttps://www.blogger.com/profile/18302009873923271496noreply@blogger.comtag:blogger.com,1999:blog-3418265334198879901.post-42471686819407353432012-08-23T18:20:38.386+05:302012-08-23T18:20:38.386+05:30This comment has been removed by the author.Debojit Saikiahttps://www.blogger.com/profile/18302009873923271496noreply@blogger.comtag:blogger.com,1999:blog-3418265334198879901.post-12886023344516219012012-06-15T16:20:43.483+05:302012-06-15T16:20:43.483+05:30This can be solved using DijkstraThis can be solved using DijkstraAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3418265334198879901.post-26723591903022643912012-02-05T22:47:55.033+05:302012-02-05T22:47:55.033+05:30@Spectator ... correct !!!@Spectator ... correct !!!Aviralhttps://www.blogger.com/profile/11920144614598355124noreply@blogger.comtag:blogger.com,1999:blog-3418265334198879901.post-46196170896512264522012-02-05T14:23:51.161+05:302012-02-05T14:23:51.161+05:30#include
#include
#include
#define FOR(k,a,b) f...#include <br />#include <br />#include <br />#define FOR(k,a,b) for(int k(a); k < (b); ++k)<br />#define FORD(k,a,b) for(int k(a-1); k >= (b); --k)<br />#define REP(k,a) for(int k=0; k < (a); ++k)<br />#define REPD(k,a) for(int k=a-1; k >-1; --k)<br />using namespace std ;<br /><br />int main()<br />{<br /> int n ;<br /> int a[50][50] ;<br /> <br /> while(1){<br /> scanf ( "%d" , &n ) ;<br /> int i , j ;<br /> REP(i,n)<br /> REP(j,n)<br /> scanf ( "%d" , &a[i][j] ) ;<br /> <br /> FOR(i,1,n)<br /> a[0][i] += a[0][i-1] ;<br /> FOR(j,1,n)<br /> a[j][0] += a[j-1][0] ;<br /> <br /> FOR(i,1,n)<br /> FOR(j,1,n){<br /> a[i][j] += min (a[i-1][j],a[i][j-1]) ;<br /> }<br /> <br /> printf("%d\n",a[n-1][n-1]);<br /> }<br /> <br /> return 0;<br />}<br />This is the solution to the first problem.Spectatorhttps://www.blogger.com/profile/03175673519287002770noreply@blogger.comtag:blogger.com,1999:blog-3418265334198879901.post-72607997814952487842012-02-03T10:16:56.581+05:302012-02-03T10:16:56.581+05:30@Anonymous .. ur solution is correct for the first...@Anonymous .. ur solution is correct for the first part of the problem.Aviralhttps://www.blogger.com/profile/11920144614598355124noreply@blogger.comtag:blogger.com,1999:blog-3418265334198879901.post-9951217032040083682012-02-03T00:08:31.785+05:302012-02-03T00:08:31.785+05:30min_s(M[m,n])=min(min_s(M[m,n-1]),min_s(M[m-1,n]))...min_s(M[m,n])=min(min_s(M[m,n-1]),min_s(M[m-1,n]))<br /> +M[m,n]Anonymousnoreply@blogger.com