fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include<limits.h>
  3. using namespace std;
  4. long long int visited[200][200],dp[200][200],dp1[200][200];
  5. char s[200][200];
  6. long long int n,t,m,i,j,k;
  7. void solve1(long long i,long long int j)
  8. {
  9. 	if(visited[i][j]==1)
  10. 		return ;
  11. 	visited[i][j]=1;
  12. 	if(i==n-1&&j==m-1)
  13. 	{
  14. 		if(s[i][j]=='1')
  15. 			dp[i][j]=0;
  16. 		else
  17. 			dp[i][j]=INT_MAX;
  18. 		return;
  19. 	}
  20. 	else if(i==n-1)
  21. 	{
  22. 		if(s[i][j]=='1')
  23. 		{
  24. 			dp[i][j]=0;
  25. 			solve1(i,j+1);
  26. 		}
  27. 		else
  28. 		{
  29. 			solve1(i,j+1);
  30. 			dp[i][j]=1+dp[i][j+1];
  31. 		}
  32. 		return;
  33. 	}
  34. 	else if(j==m-1)
  35. 	{
  36. 		if(s[i][j]=='1')
  37. 		{
  38. 			dp[i][j]=0;
  39. 			solve1(i+1,j);
  40. 		}
  41.  
  42. 		else
  43. 		{
  44. 			solve1(i+1,j);
  45. 			dp[i][j]=1+dp[i+1][j];
  46. 		}
  47. 		return;
  48. 	}
  49. 	if(s[i][j]=='1')
  50. 	{
  51. 		dp[i][j]=0;
  52. 		solve1(i+1,j);
  53. 		solve1(i,j+1);
  54. 		return ;
  55. 	}
  56. 	long long int a,b,c,d;
  57. 	solve1(i+1,j);
  58. 	solve1(i,j+1);
  59. 	dp[i][j]=1+min(dp[i+1][j],dp[i][j+1]);
  60. 	return ;
  61. }
  62. void solve2(long long i,long long int j)
  63. {
  64. 	if(visited[i][j]==1)
  65. 		return ;
  66. 	visited[i][j]=1;
  67. 	if(i==0&&j==0)
  68. 	{
  69. 		if(s[i][j]=='1')
  70. 			dp1[i][j]=0;
  71. 		else
  72. 			dp1[i][j]=INT_MAX;
  73. 		return;
  74. 	}
  75. 	else if(i==0)
  76. 	{
  77. 		if(s[i][j]=='1')
  78. 		{
  79. 			dp1[i][j]=0;
  80. 			solve2(i,j-1);
  81. 		}
  82. 		else
  83. 		{
  84. 			solve2(i,j-1);
  85. 			dp1[i][j]=1+dp1[i][j-1];
  86. 		}
  87. 		return;
  88. 	}
  89. 	else if(j==0)
  90. 	{
  91. 		if(s[i][j]=='1')
  92. 		{
  93. 			dp1[i][j]=0;
  94. 			solve2(i-1,j);
  95. 		}
  96.  
  97. 		else
  98. 		{
  99. 			solve2(i-1,j);
  100. 			dp1[i][j]=1+dp1[i-1][j];
  101. 		}
  102. 		return;
  103. 	}
  104. 	if(s[i][j]=='1')
  105. 	{
  106. 		dp1[i][j]=0;
  107. 		solve2(i-1,j);
  108. 		solve2(i,j-1);
  109. 		return ;
  110. 	}
  111. 	long long int a,b,c,d;
  112. 	solve2(i-1,j);
  113. 	solve2(i,j-1);
  114. 	dp1[i][j]=1+min(dp1[i-1][j],dp1[i][j-1]);
  115. 	return ;
  116. }
  117. int main()
  118. {
  119.  
  120. 	cin>>t;
  121. 	while(t--)
  122. 	{
  123. 		cin>>n>>m;
  124. 		for(i=0;i<n;i++)
  125. 		{
  126. 			cin>>s[i];
  127. 		}
  128. 		for(i=0;i<n;i++)
  129. 			for(j=0;j<m;j++)
  130. 				visited[i][j]=0;
  131. 		solve1(0,0);
  132. 		for(i=0;i<n;i++)
  133. 			for(j=0;j<m;j++)
  134. 				visited[i][j]=0;
  135. 		solve2(n-1,m-1);
  136. 		for(i=0;i<n;i++)
  137. 		{
  138. 			for(j=0;j<m;j++)
  139. 				cout<<min(dp1[i][j],dp[i][j])<<" ";//dp1[i][j]<<" ";
  140. 			cout<<"\n";
  141. 		}
  142.  
  143. 	}
  144. }
  145.  
Success #stdin #stdout 0s 16216KB
comments ()
stdin
copy 
2
10 160
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
6 160
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
stdout
copy 
128 127 126 125 124 123 122 121 120 119 118 117 116 115 114 113 112 111 110 109 108 107 106 105 104 103 102 101 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 2147483695 2147483694 2147483693 2147483692 2147483691 2147483690 2147483689 2147483688 2147483687 2147483686 2147483685 2147483684 2147483683 2147483682 2147483681 2147483680 2147483679 2147483678 2147483677 2147483676 2147483675 2147483674 2147483673 2147483672 2147483671 2147483670 2147483669 2147483668 2147483667 2147483666 2147483665 2147483664 2147483663 2147483662 2147483661 2147483660 2147483659 2147483658 2147483657 2147483656 
127 126 125 124 123 122 121 120 119 118 117 116 115 114 113 112 111 110 109 108 107 106 105 104 103 102 101 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 2147483694 2147483693 2147483692 2147483691 2147483690 2147483689 2147483688 2147483687 2147483686 2147483685 2147483684 2147483683 2147483682 2147483681 2147483680 2147483679 2147483678 2147483677 2147483676 2147483675 2147483674 2147483673 2147483672 2147483671 2147483670 2147483669 2147483668 2147483667 2147483666 2147483665 2147483664 2147483663 2147483662 2147483661 2147483660 2147483659 2147483658 2147483657 2147483656 2147483655 
126 125 124 123 122 121 120 119 118 117 116 115 114 113 112 111 110 109 108 107 106 105 104 103 102 101 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 2147483693 2147483692 2147483691 2147483690 2147483689 2147483688 2147483687 2147483686 2147483685 2147483684 2147483683 2147483682 2147483681 2147483680 2147483679 2147483678 2147483677 2147483676 2147483675 2147483674 2147483673 2147483672 2147483671 2147483670 2147483669 2147483668 2147483667 2147483666 2147483665 2147483664 2147483663 2147483662 2147483661 2147483660 2147483659 2147483658 2147483657 2147483656 2147483655 2147483654 
125 124 123 122 121 120 119 118 117 116 115 114 113 112 111 110 109 108 107 106 105 104 103 102 101 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 2147483692 2147483691 2147483690 2147483689 2147483688 2147483687 2147483686 2147483685 2147483684 2147483683 2147483682 2147483681 2147483680 2147483679 2147483678 2147483677 2147483676 2147483675 2147483674 2147483673 2147483672 2147483671 2147483670 2147483669 2147483668 2147483667 2147483666 2147483665 2147483664 2147483663 2147483662 2147483661 2147483660 2147483659 2147483658 2147483657 2147483656 2147483655 2147483654 2147483653 
124 123 122 121 120 119 118 117 116 115 114 113 112 111 110 109 108 107 106 105 104 103 102 101 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 2147483691 2147483690 2147483689 2147483688 2147483687 2147483686 2147483685 2147483684 2147483683 2147483682 2147483681 2147483680 2147483679 2147483678 2147483677 2147483676 2147483675 2147483674 2147483673 2147483672 2147483671 2147483670 2147483669 2147483668 2147483667 2147483666 2147483665 2147483664 2147483663 2147483662 2147483661 2147483660 2147483659 2147483658 2147483657 2147483656 2147483655 2147483654 2147483653 2147483652 
123 122 121 120 119 118 117 116 115 114 113 112 111 110 109 108 107 106 105 104 103 102 101 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 2147483690 2147483689 2147483688 2147483687 2147483686 2147483685 2147483684 2147483683 2147483682 2147483681 2147483680 2147483679 2147483678 2147483677 2147483676 2147483675 2147483674 2147483673 2147483672 2147483671 2147483670 2147483669 2147483668 2147483667 2147483666 2147483665 2147483664 2147483663 2147483662 2147483661 2147483660 2147483659 2147483658 2147483657 2147483656 2147483655 2147483654 2147483653 2147483652 2147483651 
122 121 120 119 118 117 116 115 114 113 112 111 110 109 108 107 106 105 104 103 102 101 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2147483689 2147483688 2147483687 2147483686 2147483685 2147483684 2147483683 2147483682 2147483681 2147483680 2147483679 2147483678 2147483677 2147483676 2147483675 2147483674 2147483673 2147483672 2147483671 2147483670 2147483669 2147483668 2147483667 2147483666 2147483665 2147483664 2147483663 2147483662 2147483661 2147483660 2147483659 2147483658 2147483657 2147483656 2147483655 2147483654 2147483653 2147483652 2147483651 2147483650 
121 120 119 118 117 116 115 114 113 112 111 110 109 108 107 106 105 104 103 102 101 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 2147483688 2147483687 2147483686 2147483685 2147483684 2147483683 2147483682 2147483681 2147483680 2147483679 2147483678 2147483677 2147483676 2147483675 2147483674 2147483673 2147483672 2147483671 2147483670 2147483669 2147483668 2147483667 2147483666 2147483665 2147483664 2147483663 2147483662 2147483661 2147483660 2147483659 2147483658 2147483657 2147483656 2147483655 2147483654 2147483653 2147483652 2147483651 2147483650 2147483649 
120 119 118 117 116 115 114 113 112 111 110 109 108 107 106 105 104 103 102 101 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 2147483687 2147483686 2147483685 2147483684 2147483683 2147483682 2147483681 2147483680 2147483679 2147483678 2147483677 2147483676 2147483675 2147483674 2147483673 2147483672 2147483671 2147483670 2147483669 2147483668 2147483667 2147483666 2147483665 2147483664 2147483663 2147483662 2147483661 2147483660 2147483659 2147483658 2147483657 2147483656 2147483655 2147483654 2147483653 2147483652 2147483651 2147483650 2147483649 2147483648 
119 118 117 116 115 114 113 112 111 110 109 108 107 106 105 104 103 102 101 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
https://ideone.com/s1EkQL
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!