#include<bits/stdc++.h> #include<limits.h> using namespace std; long long int visited[200][200],dp[200][200],dp1[200][200]; char s[200][200]; long long int n,t,m,i,j,k; void solve1(long long i,long long int j) { if(visited[i][j]==1) return ; visited[i][j]=1; if(i==n-1&&j==m-1) { if(s[i][j]=='1') dp[i][j]=0; else dp[i][j]=INT_MAX; return; } else if(i==n-1) { if(s[i][j]=='1') { dp[i][j]=0; solve1(i,j+1); } else { solve1(i,j+1); dp[i][j]=1+dp[i][j+1]; } return; } else if(j==m-1) { if(s[i][j]=='1') { dp[i][j]=0; solve1(i+1,j); } else { solve1(i+1,j); dp[i][j]=1+dp[i+1][j]; } return; } if(s[i][j]=='1') { dp[i][j]=0; solve1(i+1,j); solve1(i,j+1); return ; } long long int a,b,c,d; solve1(i+1,j); solve1(i,j+1); dp[i][j]=1+min(dp[i+1][j],dp[i][j+1]); return ; } void solve2(long long i,long long int j) { if(visited[i][j]==1) return ; visited[i][j]=1; if(i==0&&j==0) { if(s[i][j]=='1') dp1[i][j]=0; else dp1[i][j]=INT_MAX; return; } else if(i==0) { if(s[i][j]=='1') { dp1[i][j]=0; solve2(i,j-1); } else { solve2(i,j-1); dp1[i][j]=1+dp1[i][j-1]; } return; } else if(j==0) { if(s[i][j]=='1') { dp1[i][j]=0; solve2(i-1,j); } else { solve2(i-1,j); dp1[i][j]=1+dp1[i-1][j]; } return; } if(s[i][j]=='1') { dp1[i][j]=0; solve2(i-1,j); solve2(i,j-1); return ; } long long int a,b,c,d; solve2(i-1,j); solve2(i,j-1); dp1[i][j]=1+min(dp1[i-1][j],dp1[i][j-1]); return ; } int main() { cin>>t; while(t--) { cin>>n>>m; for(i=0;i<n;i++) { cin>>s[i]; } for(i=0;i<n;i++) for(j=0;j<m;j++) visited[i][j]=0; solve1(0,0); for(i=0;i<n;i++) for(j=0;j<m;j++) visited[i][j]=0; solve2(n-1,m-1); for(i=0;i<n;i++) { for(j=0;j<m;j++) cout<<min(dp1[i][j],dp[i][j])<<" ";//dp1[i][j]<<" "; cout<<"\n"; } } }
2 10 160 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 6 160 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
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