1895: Landlocked
Time Limit: 5 Sec Memory Limit: 128 MB
[ Submit][ Status][ Web Board]
Description
Canada is not a landlocked country: the country touches at least one ocean (in fact, it touches three).
There are 46 countries (including Bolivia and Mongolia, for example) which are landlocked. That is, they do not touch an ocean, but by going through one other country, an ocean can be reached. For example, a person in Mongolia can get to an ocean by passing through Russia.
Liechtenstein and Uzbekistan are the only two countries in the world which are land-landlocked. That is, not only are they land-locked, but all countries which surround these two countries are land-locked countries. Thus, one would have to pass through at least two different countries when leaving Uzbekistan before arriving at an ocean.
Your task is to determine how landlocked each country is on a given map. We say that a country is not landlocked (recorded as 0) if it touches water in any adjacent cell in either a horizontal, vertical, or diagonal direction. If a country is landlocked, you must calculate the minimum number of borders that one must cross in order to travel from the country to water. Each step of such a journey must be to a cell that is adjacent in either a horizontal, vertical, or diagonal direction. Crossing a border is defined as taking a step from a cell in one country to an adjacent cell in a different country.
Note that countries may not be connected to themselves (as in a country formed of islands). In this case, the landlocked value for the country is the minimal of each connected region of the country.
Input
The first line contains N and M (1 ≤ N, M ≤ 1000).
On each of the next N lines, there are M capital letters. Each country will be represented by a unique letter, with the exception that the letter W is reserved to indicate the water in the oceans or seas that will be used to determine the how landlocked each country is.
Output
The output consists of the country letter followed by a space, followed by the landlockedness for that particular country. Output should be in alphabetical order.
Sample Input
7 10 WWWWWCCDEW WWWWCCEEE W WTWWWCCCCW WWFFFFFFWW WWFAAAAFWW WWFABCAFFW WWFAAAAFWW
Sample Output
A 1 B 2 C 0 D 1 E 0 F 0 T 0
【分析】
題意：給出一個地圖"W'是海洋，其他字元都是國家，問你每個國家想要到達海洋最少需要經過多少國家。 看題意就猜的到是最短路...隻不過這個最短路有點...考思路吧算是.. 首先,可以反過來想，國家到達海洋，反過來就是海洋到達國家，因為我們如果從國家出發，那其實很難找起點...但是從海洋出發就簡單了，起點全是“W”。 因為每個國家是一個聯通塊...是以這裡需要一個dfs，剩下的就是單純的bfs了..以所有單獨的海洋塊為起點開始展開，碰到新的國家就距離+1并且入隊，否則就直接dfs搜尋遍整個目前國家 【代碼】
#include<iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;
char a[1010][1010];
int vis[1010][1010];
int value[1010][1010];
int fx[8][2]={{1, 0},
{-1, 0},
{0, 1},
{0, -1},
{1, 1},
{1, -1},
{-1, 1},
{-1, -1}};
struct xx{
int x,y,v;
}t;
int deep,n,m;
char now;
queue<xx>q[100];
void find(int x,int y,int val)
{
vis[x][y]=1;
value[x][y]=val;
for(int i=0;i<8;i++)
{
int xx=x+fx[i][0];
int yy=y+fx[i][1];
if(xx<0||yy<0||xx>=n||yy>=m||vis[xx][yy]==1) continue;
if(a[xx][yy]==now)
find(xx,yy,val);
else
{
t.x=xx;t.y=yy;t.v=val+1;
q[deep].push(t);
}
}
}
int f[30];
int main()
{
while(~scanf("%d%d",&n,&m))
{
memset(vis,0,sizeof(vis));
for(int i=0;i<n;i++) scanf("%s",a[i]);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(a[i][j]=='W')
{
t.x=i;t.y=j;t.v=-1;
q[0].push(t);
}
memset(value,-1,sizeof(value));
for(int i=0;!q[i].empty();i++)
{
while(!q[i].empty())
{
xx tt=q[i].front();
q[i].pop();
if(vis[tt.x][tt.y]==1) continue;
deep=i;
now=a[tt.x][tt.y];
find(tt.x,tt.y,tt.v);
}
}
memset(f,INF,sizeof(f));
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
f[a[i][j]-65]=min(f[a[i][j]-65],value[i][j]);
for(int i=0;i<30;i++)
if (f[i]!=INF && i!=22)
printf("%c %d\n",i+65,f[i]);
}
}