Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define int long long
- using namespace std;
- const int mn = 35;
- int n;
- int a;
- int b;
- int x;
- int y;
- string s;
- int i;
- int j;
- int k;
- vector<string> grid(mn);
- vector<vector<int>> dist(mn, vector<int>(mn, 1000000000));
- signed main() {
- freopen("distant.in", "r", stdin);
- freopen("distant.out", "w", stdout);
- cin>>n>>a>>b;
- grid.resize(n);
- dist.resize((n*n));
- for(i=0;i<n;i++) {
- cin>>s;
- grid.at(i) = s;
- dist.at(i).resize(n);
- }
- for(i=0;i<(n*n);i++)
- dist[i][i] = 0;
- for(i=0;i<n;i++) {
- for(j=0;j<(n-1);j++) {
- x = i;
- x *= n;
- x += j;
- if(grid[i][j] == grid[i][j+1]) {
- dist[x][x+1] = a;
- dist[x+1][x] = a;
- }
- else {
- dist[x][x+1] = b;
- dist[x+1][x] = b;
- }
- }
- }
- for(j=0;j<n;j++) {
- for(i=0;i<(n-1);i++) {
- x = i;
- x *= n;
- x += j;
- if(grid[i][j] == grid[i+1][j]) {
- dist[x][x+n] = a;
- dist[x+n][x] = a;
- }
- else {
- dist[x][x+n] = b;
- dist[x+n][x] = b;
- }
- }
- }
- for(k=0;k<(n*n);k++) {
- for(i=0;i<(n*n);i++) {
- for(j=0;j<(n*n);j++)
- dist[i][j] = min(dist[i][j], (dist[i][k] + dist[k][j]));
- }
- }
- x = -1;
- for(i=0;i<(n*n);i++) {
- for(j=0;j<(n*n);j++)
- x = max(x, dist[i][j]);
- }
- cout<<x<<endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
