My issue
Can anyone suggest a related video or concept to solve this problem?
I attempted to solve the problem in the contest using the Breadth First Search (BFS) algorithm
My code
#include<bits/stdc++.h>
#define int long long
#define ff first
#define ss second
#define pb push_back
const int mod = 1e9 + 7;
using namespace std;
int32_t main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--) {
int n, m, k;
cin >> n >> m >> k;
int a[n][m];
int vis[n][m];
int ano[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[i][j];
vis[i][j] = 0;
ano[i][j] = 0;
}
}
char pos[n][m];
for (int i = 0; i < n; i++) {
string s; cin >> s;
for (int j = 0; j < m; j++) {
pos[i][j] = s[j];
if (pos[i][j] == '1') vis[i][j] = 1;
}
}
int row[] = { 0, -1};
int col[] = { -1, 0};
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (pos[i][j] == '1' && vis[i][j] == 1) {
pos[i][j] = '1';
for (int kk = 0; kk < 2; kk++) {
int rr = i + row[kk];
int cc = j + col[kk];
if (rr >= 0 && rr < n && cc >= 0 && cc < m) {
ano[rr][cc] ++;
pos[rr][cc] = '1';
}
}
}
}
}
vector<vector<int>>dis(n, vector<int>(m, 1e18));
queue<pair<int, int>>q;
q.push({0, 0});
dis[0][0] = 0;
int row1[2] = {0, 1};
int col1[2] = {1, 0};
while (!q.empty()) {
int x = q.front().ff;
int y = q.front().ss;
// cout << x << " " << y << endl;
q.pop();
for (int i = 0; i < 2; i++) {
int rr = x + row1[i];
int cc = y + col1[i];
if (rr >= 0 && rr < n && cc >= 0 && cc < m) {
int extra = k * ano[rr][cc];
if ((a[rr][cc] + dis[x][y] + extra) < dis[rr][cc]) {
dis[rr][cc] = dis[x][y] + a[rr][cc] + extra;
q.push({rr, cc});
}
}
}
}
cout << dis[n - 1][m - 1] << endl;
}
return 0;
}
Problem Link: Go Away, Goose! Practice Coding Problem - CodeChef