Problem link :
Author : kingavrun
Tester : deo002
Editorilist : kingvarun
DIFFICULTY :
Easy
PROBLEM :
Given matrix and a string ,your task is to make all paths of from top left to bottom right of matrix as same as given string by changing elements either in matrix or in string . You have to minimize the cost for making this equal.
EXPLANATION :
We have to store the number of 1 and number of 0 in two different vectors such that we able to maintain the count of 1 and 0 for each step of the all possible paths, than we have minimize the cost by check which is suitable
1 To replace all incorrect elements of matrix by same as string element
2 To change string element and corresponding to that change some matrix elements also,
TIME COMPLEXITY :
O(T * N * M)
Setter Solution
setter solution
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
int t;
cin >> t;
while(t--)
{
ll n, m, i, j, ans=0, cost1, cost2;
cin >> n >> m;
ll a[n][m];
vector<ll> store1(n+m-1,0) , store0(n+m-1,0);
for(i = 0; i < n; i++)
{
for(j = 0; j < m; j++)
{
cin >> a[i][j];
if(a[i][j]==0) // storing count of 0 at each step of all paths
store0[i+j]++;
else
store1[i+j]++; // storing count of 1 at each step of all paths
}
}
string s;
cin >> s;
cin >> cost1 >> cost2;
for(i = 0; i < n+m-1; i++)
{
if(s[i]=='1')
{
ans += min((cost1 * store0[i]), ((cost1 * store1[i])+cost2) );
}
else
{
ans += min((cost1 * store1[i]), ((cost1 * store0[i])+cost2) );
}
}
cout << ans << "\n";
}
return 0;
}