[URI ONLINE JUDGE] – 1714 – Letters

Link: https://www.urionlinejudge.com.br/judge/en/problems/view/1714

The parks in the City of Logic are always a grid of N ×N squares (2 ≤ N ≤ 100), where each square has one of the first 10 ASCII letters, abcdefghijABCDEFGHIJ, in either lowercase or uppercase format. People from the City of Logic proudly follow only consistent paths when crossing parks. For example, if they step over a lowercase c, they will not allow themselves stepping over an uppercase C afterwards. To define this more precisely, a consistent path is a sequence of squares satisfying: consecutive squares are orthogonally adjacent; no letter occurs in both lowercase and uppercase format. That is to say, either a letter is not in the sequence at all, or it occurs only in lowercase, or only in uppercase format.

You have to write a program to help the people from the City of Logic to find the length a shortest consistent path between the square with coordinates (1, 1), in the upper left corner, and the square with coordinates (N, N ), in the lower right corner. For the example park above, the shortest consistent path has length 13.

Input

The input contains several test cases. The first line of a test case has a integer N (2 ≤ N ≤ 100), the size of the park. The next N lines contain, each one, a sequence of N letters, defining the park.

Output

For each test case in the input your program must output one line containing one integer, the length of a shortest consistent path. If there is no consistent path, output -1.

Sample Input Sample Output
7

aAaaaaa

aAaaaAa

aAaaaAA

aaAaAaa

AaAaaAa

aaAAaAa

aaaaaAa

-1

 

solution:

 

<br />#include <bits/stdc++.h>

#define INF 999999

using namespace std;
typedef pair<int, int> ii;

int dr[] = {1, -1, 0, 0};
int dc[] = {0, 0, -1, 1};

int d[105][105];
vector g;
int n;

int val(int i, int j)
{
return i >= 0 && i < n && j >= 0 && j < n;
}
int value(char c)
{
return tolower(c) - 'a';
}

int bfs(int mask)
{
queue< ii > q;
int result;
q.push(make_pair(0, 0));
ii u;
for (int i = 0 ; i < n ; ++i) for (int j = 0 ; j < n ; ++j)
d[i][j] = INF;

d[0][0] = 1;

char c = g[0][0];
int vl = value(c);
if (c == tolower(c)) result = (1 << vl);
else result = 0;
if ((mask & (1 << vl)) != result) return INF;

while (!q.empty())
{
u = q.front();
q.pop();
int x = u.first;
int y = u.second;
for (int i = 0 ; i < 4; ++i)
{
if (val(x + dr[i], y + dc[i]))
{
c = g[x + dr[i]][y + dc[i]];
vl = value(c);
if (c == tolower(c)) result = (1 << vl);
else result = 0;
if ((mask & (1 << vl)) == result) { if (d[x + dr[i]][y + dc[i]] > d[x][y] + 1)
{
d[x + dr[i]][y + dc[i]] = d[x][y] + 1;
q.push(make_pair(x + dr[i], y + dc[i]));
}
}
}
}
}
return d[n - 1][n - 1];
}

int main()
{
string s;

ios_base :: sync_with_stdio(0); cin.tie(0);
cin >> n;

for (int i = 0 ; i < n; ++i) { cin >> s;
g.push_back(s);
}

int ans = INF;
for (int i = 0 ; i < (1 << 10); ++i)
{
ans = min(ans, bfs(i));
}

if (ans != INF)
cout << ans << '\n';
else cout << -1 << '\n';

}

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s