Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1043
The square field consists of M × M cells. Each cell is colored in one of three colors (1,2,3). The initial state is chosen in one of the cells of color 1. In each step one allowed to move one cell up, down, left or right remaining inside the field. You are to define the minimal amount of steps one should make to get a cell of color 3 independent on the initial state. Note that the field contains at least one cell of color 1 and at least one cell of color 3. Input The input consists of several input blocks. The first line of each block contains integer M, the size of the field. Then there are M lines with colors of the cells. Output For each input block the output should consist of one line with the integer, the minimal amount of steps one should make to get a cell of color 3 independent on the initial state.
Sample Input 4 1223 2123 2213 3212 2 12 33
Sample Output 3 1
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
// complete search between 2 coord O(O*T), nums of one and three
using namespace std;
int main()
{
int M;
char cells[101][101];
while(scanf("%d",&M) != EOF){
for(int i=0;i i&It M;i++) scanf("%s",cells[i]);
vector<<int,int>> ones;
vector<<int,int>> threes;
for(int i=0;i i&It M;i++)
for(int j=0;j i&It M;j++)
if(cells[i][j]=='1'){
ones.push_back({i,j});
}else if(cells[i][j]=='3'){
threes.push_back({i,j});
}
int res = INT_MIN;
for(auto& p1 : ones){
int best = INT_MAX;
for(auto& p2 : threes)
best = min(best,abs(p1.first-p2.first)+abs(p1.first-p2.second));
res = max(best,res);
}
printf("%d\n",res);
}
return 0;
} Input
1223
2123
2213
3212
2
12
33
Output
1
Demonstration
UVA Online Judge solution - 10102 - The path in the colored field - UVA Online Judge solution in C,C++,Java