# 89 条题解

• @ 2017-10-03 12:31:01

思路: Floyd (暴力).
时间复杂度: O(n^6).
空间复杂度: O(n^4).
代码:

``````#include <bits/stdc++.h>
using namespace std;

const int maxn = 25, INF = 0x3f3f3f3f;
string s[maxn];
int n, m, res = INF, dp[maxn][maxn][maxn][maxn];
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};

int main() {
ios::sync_with_stdio(false);
memset(dp, INF, sizeof(dp));
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> s[i];
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
dp[i][j][i][j] = 0;
for (int k = 0; k < 4; k++) {
int x = i + dx[k], y = j + dy[k];
if (x >= 0 && x < n && y >= 0 && y < m) {
dp[i][j][x][y] = (s[i][j] != s[x][y]);
}
}
}
}
// floyd
for (int kx = 0; kx < n; kx++) {
for (int ky = 0; ky < m; ky++) {
for (int ix = 0; ix < n; ix++) {
for (int iy = 0; iy < m; iy++) {
for (int jx = 0; jx < n; jx++) {
for (int jy = 0; jy < m; jy++) {
dp[ix][iy][jx][jy] = min(dp[ix][iy][jx][jy], dp[ix][iy][kx][ky] + dp[kx][ky][jx][jy]);
}
}
}
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < m; j++) {
res = min(res, dp[0][i][n - 1][j]);
}
}
cout << res + 1 << endl;
return 0;
}
``````

评测结果:
Accepted.

• @ 2019-05-12 11:52:32

第一眼看过去，以为是DP，搞得我复习了一遍DP才拿到了75分。DP如下，大家应该很快能看出来DP在这道题里有什么不妥。

``````#include <iostream>

using namespace std;

int m,n;
char brg[21][21];
int dp[21][21];

int main()
{
cin>>m>>n;
int i,j;
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
cin>>brg[i][j];
}
}
for(i=0;i<n;i++)
{
dp[0][i]=1;
}
for(i=1;i<m;i++)
{
for(j=0;j<n;j++)
{
if(brg[i][j]==brg[i-1][j])
{
dp[i][j]=dp[i-1][j];
}
else
{
dp[i][j]=dp[i-1][j]+1;
}
}
for(j=1;j<n;j++)
{
if(brg[i][j]==brg[i][j-1])
{
dp[i][j]=min(dp[i][j],dp[i][j-1]);
}
else
{
dp[i][j]=min(dp[i][j],dp[i][j-1]+1);
}
}
for(j=n-1;j>0;j--)
{
if(brg[i][j]==brg[i][j-1])
{
dp[i][j]=min(dp[i][j],dp[i][j-1]);
}
else
{
dp[i][j]=min(dp[i][j],dp[i][j-1]+1);
}
}
}
int ans=1e9;
for(i=0;i<n;i++)
{
ans=min(ans,dp[m-1][i]);
}
cout<<ans<<endl;
return 0;
}
``````

之后改用BFS秒杀，所有的点都是1ms。

``````#include <iostream>
#include <cstring>

using namespace std;

int m,n;
char brg[22][21];
int dp[22][21];
int depth=0;
int ans=-1;
int check;

void bfs(int x,int y)
{
if(x==m)
{
ans=dp[x][y];
}
if(x>0)
{
if(brg[x-1][y]==brg[x][y])
{
if(dp[x-1][y]>dp[x][y])
{
dp[x-1][y]=dp[x][y];
check++;
}
}
else
{
if(dp[x-1][y]>dp[x][y]+1)
{
dp[x-1][y]=dp[x][y]+1;
check++;
}
}
}
if(x<m)
{
if(brg[x+1][y]==brg[x][y])
{
if(dp[x+1][y]>dp[x][y])
{
dp[x+1][y]=dp[x][y];
check++;
}
}
else
{
if(dp[x+1][y]>dp[x][y]+1)
{
dp[x+1][y]=dp[x][y]+1;
check++;
}
}
}
if(y>0)
{
if(brg[x][y-1]==brg[x][y])
{
if(dp[x][y-1]>dp[x][y])
{
dp[x][y-1]=dp[x][y];
check++;
}
}
else
{
if(dp[x][y-1]>dp[x][y]+1)
{
dp[x][y-1]=dp[x][y]+1;
check++;
}
}
}
if(y<n-1)
{
if(brg[x][y+1]==brg[x][y])
{
if(dp[x][y+1]>dp[x][y])
{
dp[x][y+1]=dp[x][y];
check++;
}
}
else
{
if(dp[x][y+1]>dp[x][y]+1)
{
dp[x][y+1]=dp[x][y]+1;
check++;
}
}
}
}

int main()
{
cin>>m>>n;
int i,j;
memset(dp,63,sizeof(dp));
for(i=1;i<=m;i++)
{
for(j=0;j<n;j++)
{
cin>>brg[i][j];
}
}
for(i=0;i<n;i++)
{
brg[0][i]='0';
dp[0][i]=0;
}
while(true)
{
check=0;
for(i=0;i<=m;i++)
{
for(j=0;j<n;j++)
{
if(dp[i][j]==depth)
{
bfs(i,j);
}
}
}
if(ans!=-1)
{
break;
}
if(check==0)
{
depth++;
}
}
cout<<ans<<endl;
return 0;
}
``````
• @ 2018-02-09 00:15:38

BFS求解
1. 给每一个块编号（第一遍dfsv）
2. 邻接表设相邻块编号为true（第二遍dfsbgraph）
3. BFS搜到结束节点（ED）后输出步数并退出

``````#include<cstdio>
#include<iostream>
#include<queue>
#define MAXN 25
#define INF 2100000000
#define MAXC 500
#define ST 497
#define ED 496
using namespace std;

typedef pair<int, int> pii;
int n, m;
const int dx[5] = {0, -1, 0, 1}, dy[5] = {1, 0, -1, 0};
char cm[MAXN][MAXN];
bool visv[MAXN][MAXN] = {false}, visf[MAXN][MAXN] = {false};
bool adjm[MAXC][MAXC] = {false}, vbfs[MAXC] = {false};
int blockid[MAXC][MAXC] = {0}, cnt = 1;

void dfsf(char c, int y, int x, int fill){
if(y < 1 || y > m || x < 1 || x > n || (visv[y][x] && cm[y][x] == c) || cm[y][x] != c){
return;
}
visv[y][x] = true;
blockid[y][x] = fill;
int tx, ty;
for(int i=0; i<4; i++){
tx = x + dx[i];
ty = y + dy[i];
dfsf(c, ty, tx, fill);
}
return;
}

void dfsbgraph(char c, int y, int x, int fill){
if(y < 1 || y > m || x < 1 || x > n || (visf[y][x] && cm[y][x] == c)){
return;
}
if(fill!=blockid[y][x]){
return;
}
visf[y][x] = true;
int tx, ty;
for(int i=0; i<4; i++){
tx = x + dx[i];
ty = y + dy[i];
dfsbgraph(c, ty, tx, fill);
}
return;
}

int main(){

cin >> m >> n;

for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
// scanf("%c", &cm[i][j]);
cin >> cm[i][j];
}
}

for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
dfsf(cm[i][j], i, j, cnt++);
}
}

for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
dfsbgraph(cm[i][j], i, j, blockid[i][j]);
}
}

for(int j=1; j<=n; j++){
}

queue<pii> q;
q.push(make_pair(ST, 0));
while(!q.empty()){
pii p = q.front();
q.pop();
int node = p.first;
if(vbfs[node]) continue;
int steps = p.second;
// cout << node << " " ;
if(node == ED){
cout << steps-1 << endl;
return 0;
}
vbfs[node] = true;
for(int i=0; i<=499; i++){
q.push(make_pair(i, steps+1));
}
}
}

return 0;
}

``````

评测情况
PS：BFS快一些

`````` Accepted
#   状态  耗时  内存占用
#1  Accepted    3ms     384.0 KiB
#2  Accepted    3ms     384.0 KiB
#3  Accepted    3ms     352.0 KiB
#4  Accepted    2ms     360.0 KiB
#5  Accepted    3ms     384.0 KiB
#6  Accepted    3ms     384.0 KiB
#7  Accepted    2ms     356.0 KiB
#8  Accepted    3ms     356.0 KiB
#9  Accepted    3ms     256.0 KiB
#10     Accepted    3ms     512.0 KiB
#11     Accepted    1ms     360.0 KiB
#12     Accepted    3ms     488.0 KiB
#13     Accepted    3ms     488.0 KiB
#14     Accepted    3ms     508.0 KiB
#15     Accepted    3ms     496.0 KiB
#16     Accepted    3ms     512.0 KiB
#17     Accepted    4ms     512.0 KiB
#18     Accepted    4ms     628.0 KiB
#19     Accepted    3ms     512.0 KiB
#20     Accepted    2ms     632.0 KiB
``````
• @ 2018-11-08 18:19:52

dijkstra

``````#include<iostream>
#include<cstdio>
using namespace std;
int abs(int a){
return a>0?a:-a;
}
int main(){
int m,n;
char map[22*22]={0};
int a[22*22][22*22]={0};
int f[22*22]={0};
bool v[22*22]={0};
cin>>m>>n;
for(int i=0;i<=m*n+1;i++)
for(int j=0;j<=m*n+1;j++)
a[i][j]=2147000000;
for(int i=0;i<m;i++){
for(int j=1;j<=n;j++){
cin>>map[i*n+j];
if(i>0)
if(map[i*n+j]==map[i*n+j-n])
a[i*n+j][i*n+j-n]=a[i*n+j-n][i*n+j]=0;
else
a[i*n+j][i*n+j-n]=a[i*n+j-n][i*n+j]=1;
if(j>1)
if(map[i*n+j]==map[i*n+j-1])
a[i*n+j][i*n+j-1]=a[i*n+j-1][i*n+j]=0;
else
a[i*n+j][i*n+j-1]=a[i*n+j-1][i*n+j]=1;
}
}
for(int i=1;i<=n;i++){
a[0][i]=a[i][0]=1;
a[m*n+1][m*n+1-i]=a[m*n+1-i][m*n+1]=0;
}
v[0]=1;
f[0]=0;
for(int i=1;i<=n*m+1;i++)
if(a[0][i]!=2147000000)
f[i]=a[0][i];
for(int i=1;i<=n*m+1;i++){
int w=0;
int min_=0;
for(int j=1;j<=n*m+1;j++)
if(v[j]==0&&(f[j]!=0&&(min_==0||f[j]<=min_))){
w=j;
min_=f[j];
}
v[w]=1;
for(int j=1;j<=n*m+1;j++)
if(v[j]==0&&(f[j]>f[w]+a[w][j]||f[j]==0))
f[j]=f[w]+a[w][j];
}
printf("%d",f[n*m+1]);
return 0;
}
``````
• @ 2018-04-16 21:47:02

遍历图上各字母的分布情况，建立领接矩阵，最后BFS，结果Accepted.

• @ 2017-10-09 19:16:59

SPFA.

``````#include <iostream>
#include <queue>
using namespace std;
#define For(aHJEfaks, fwbjkWK, AENGIBv) for (int aHJEfaks = fwbjkWK; aHJEfaks <= AENGIBv; ++aHJEfaks)
#define For2(aHJEfaks, fwbjkWK, AENGIBv) for (auto aHJEfaks = fwbjkWK; aHJEfaks != AENGIBv; ++aHJEfaks)
int n, m;
char a[100][100];
int di[100][100];
typedef pair<int, int> pa;
queue<pa> sp;
bool iq[100][100];
bool le(pa x){
return (0 < x.first && x.first <= n && 0 < x.second && x.second <= m);
}
int main(){
cin >> n >> m;
For(i, 1, n){
For(j, 1, m)
{
cin >> a[i][j];
}
}
For(i, 1, n){
For(j, 1, m)
{
di[i][j] = 9999999;
}
}
For(i, 1, m){
iq[1][i] = true;
sp.emplace(1, i);
di[1][i] = 1;
}
while (!sp.empty()){
pa to = sp.front();
sp.pop();
iq[to.first][to.second] = false;
int x = to.first, y = to.second;
if (le(make_pair(x - 1, y))){
if (a[x - 1][y] == a[x][y]){
if (di[x - 1][y] > di[x][y]){
di[x - 1][y] = di[x][y];
if (!iq[x - 1][y]){
sp.push(make_pair(x - 1, y));
iq[x - 1][y] = true;
}
}
}
if (a[x - 1][y] != a[x][y]){
if (di[x - 1][y] > di[x][y] + 1){
di[x - 1][y] = di[x][y] + 1;
if (!iq[x - 1][y]){
sp.push(make_pair(x - 1, y));
iq[x - 1][y] = true;
}
}
}

}

if (le(make_pair(x + 1, y))){
if (a[x + 1][y] == a[x][y]){
if (di[x + 1][y] > di[x][y]){
di[x + 1][y] = di[x][y];
if (!iq[x + 1][y]){
sp.push(make_pair(x + 1, y));
iq[x + 1][y] = true;
}
}
}
if (a[x + 1][y] != a[x][y]){
if (di[x + 1][y] > di[x][y] + 1){
di[x + 1][y] = di[x][y] + 1;
if (!iq[x + 1][y]){
sp.push(make_pair(x + 1, y));
iq[x + 1][y] = true;
}
}
}

}

if (le(make_pair(x, y - 1))){
if (a[x][y - 1] == a[x][y]){
if (di[x][y - 1] > di[x][y]){
di[x][y - 1] = di[x][y];
if (!iq[x][y - 1]){
sp.push(make_pair(x, y - 1));
iq[x][y - 1] = true;
}
}
}
if (a[x][y - 1] != a[x][y]){
if (di[x][y - 1] > di[x][y] + 1){
di[x][y - 1] = di[x][y] + 1;
if (!iq[x][y - 1]){
sp.push(make_pair(x, y - 1));
iq[x][y - 1] = true;
}
}
}

}

if (le(make_pair(x, y + 1))){
if (a[x][y + 1] == a[x][y]){
if (di[x][y + 1] > di[x][y]){
di[x][y + 1] = di[x][y];
if (!iq[x][y + 1]){
sp.push(make_pair(x, y + 1));
iq[x][y + 1] = true;
}
}
}
if (a[x][y + 1] != a[x][y]){
if (di[x][y + 1] > di[x][y] + 1){
di[x][y + 1] = di[x][y] + 1;
if (!iq[x][y + 1]){
sp.push(make_pair(x, y + 1));
iq[x][y + 1] = true;
}
}
}

}
}
int ans = di[n][1];
For(i, 2, m){
ans = min(ans, di[n][i]);
}
cout << ans << endl;

//    For(i, 1, n) {
//        For(j, 1, m) {
//            cout << di[i][j] << ' ';
//        }
//        cout << endl;
//    }
return 0;
}
``````
• @ 2017-03-25 22:30:30

极端暴力的floyd
g[i][j][ii][jj]代表i,j到ii,jj的距离，相邻的点之间建立边，字母相同长为1，否则为0，然后g[i][j][i][j]定义为0

``````#include <stdio.h>
#include <algorithm>
#include <queue>
#include <cstring>
#include <iostream>
#include <string>
#include <map>
#include <ciso646>
#include <stack>
#include <cstdlib>
using namespace std;
const int maxn = 1000000;

int g[22][22][22][22];
int nx[4] = { 0,0,1,-1 }, ny[4] = { 1,-1,0,0 };
char c[22][22];
int dis[1001];
int n, m, i, j, k, l;
int ans = maxn;

int main()
{
scanf("%d%d", &n, &m);

for (i = 0;i <= 21;i++)
for (j = 0;j <= 21;j++)
for (k = 0;k <= 21;k++)
for (l = 0;l <= 21;l++)
{
if (i != k || j != l)
g[i][j][k][l] = maxn;
}
for (i = 1;i <= n;i++)
for (j = 1;j <= m;j++)
cin >> c[i][j];

for (i = 1;i <= n;i++)
for (j = 1;j <= m;j++)
for (k = 0;k < 4;k++)
{
int x = nx[k] + i;
int y = ny[k] + j;
if (c[i][j] == c[x][y])
g[i][j][x][y] = 0;
else g[i][j][x][y] = 1;
}

int ii, jj;

for (i = 1;i <= n;i++)
for (j = 1;j <= m;j++)
for (k = 1;k <= n;k++)
for (l = 1;l <= m;l++)
for (ii = 1;ii <= n;ii++)
for (jj = 1;jj <= m;jj++)
g[i][j][ii][jj] = min(g[i][j][ii][jj], g[i][j][k][l] + g[k][l][ii][jj]);

for (i = 1;i <= m;i++)
for (j = 1;j <= m;j++)
{
ans = min(ans, g[1][i][n][j]);
ans = min(ans, g[n][i][1][j]);
}

printf("%d", ans + 1);

system("pause");

return 0;
}
``````
• @ 2015-01-29 19:01:22

注意单行,单列,以及只有一个格子的情况!
floyd不会爆...但是记得初始化....自己到自己的距离要写为0....否则输出结果需特判

• @ 2012-08-08 13:06:18

一个小DP，虽然没全过，但过了60%。。

program p1409;var n,m,i,j,min:longint;    a:array[0..22,0..22] of char;    dp:array[0..22,0..22] of longint;begin  readln(n,m);  for i:=1 to n do    begin      for j:=1 to m do        read(a);      readln;    end;  fillchar(dp,sizeof(dp),\$F7);  for i:=1 to m do    dp[n,i]:=1;  for i:=n-1 downto 1 do    for j:=1 to m do      if a=a then dp:=dp        else dp:=dp+1;  min:=maxlongint;  for i:=1 to m do    if dp[1,i]

• @ 2009-11-09 08:47:04

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 493ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 508ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 0ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 524ms

├ 测试数据 15：答案正确... 0ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 524ms

├ 测试数据 18：答案正确... 524ms

├ 测试数据 19：答案正确... 0ms

├ 测试数据 20：答案正确... 493ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：3066ms

懒得敲spfa了，，floyd凑合过了。。。

program p1406;

var a:array[0..500,0..500] of char;

w:array[0..500,0..500] of longint;

i,j,k,l,m,n:longint;

begin

for i:=1 to m do begin

l:=m*n+1;

for i:=0 to l do

for j:=0 to l do if ij then w:=1000;

for i:=1 to m do

for j:=1 to n do

begin

if i>1 then

if a=a then

w[(i-1)*n+j,(i-2)*n+j]:=0 else w[(i-1)*n+j,(i-2)*n+j]:=1;

if i1 then

if a=a then

w[(i-1)*n+j,(i-1)*n+j-1]:=0 else w[(i-1)*n+j,(i-1)*n+j-1]:=1;

if j

• @ 2009-11-06 21:13:54

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 0ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：答案正确... 0ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 0ms

├ 测试数据 18：答案正确... 0ms

├ 测试数据 19：答案正确... 0ms

├ 测试数据 20：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

操，一个循环搞错，死循环了一个下午，和女朋友吃完饭，回来一看就发现了

晕死

program p1406;

const d:array[1..4,1..2]of integer=((1,0),(-1,0),(0,1),(0,-1));

var max,s,k,m,n,i,j,now:longint;

a:array[-1..23,-1..23]of char;

num:array[-1..23,-1..23]of longint;

aa:array[1..500,1..500]of integer;

v:array[1..500]of boolean;

dd:array[1..500]of longint;

procedure floodfill(x,y,ss:longint);

var i,xx,yy:longint;

begin

num[x,y]:=ss;

for i:=1 to 4 do

begin

xx:=x+d;

yy:=y+d;

if (a[xx,yy]=a[x,y])and(num[xx,yy]=-1) then floodfill(xx,yy,ss);

end;

end;

procedure built;

var i,j,k,ii,jj:longint;

begin

fillchar(aa,sizeof(aa),0);

for i:=0 to m+1 do

for j:=1 to n do

for k:=1 to 4 do

begin

ii:=i+d[k,1];

jj:=j+d[k,2];

if (a[ii,jj]a)and(a[ii,jj]'-') then aa[num,num[ii,jj]]:=1;

end;

end;

procedure dijkstra;

var i,j:longint;

begin

fillchar(v,sizeof(v),false);

fillchar(dd,sizeof(dd),0);

s:=1;v:=true;

repeat

max:=maxlongint;k:=0;

for i:=1 to now do

begin

if (aa=1)and((dd+aa

• @ 2009-11-02 20:36:35

40MIN的DEBUG。。。代价惨痛啊！写了两次都没花我20MIN。。。

我的错误是：if f[x,y]

• @ 2009-10-29 11:48:52

开始没理解题意想错...

后来用floyd超爆...

最后,

floodfill预处理+spfa

同样的评测机第一次超时第二次0ms...

• @ 2009-10-21 07:31:48

这道题的范围确实只有20*20(n=20).但如果使用floyd的话节点数就是20*20(n=20*20),故要开[0..4xx,0..4xx]的邻接矩阵。

不建议采用floyd这种时间复杂度较高的算法(O(N*N)^3)。

推荐解法:floodfill(就是种子填充）+BFS遍历即可。O(n^3).

贴下我的程序：

//PROGRAM MEET

//DATE 2009-10-20

const

oo=32766;

dx:array[1..4] of longint=(0,0,-1,1);

dy:array[1..4] of longint=(-1,1,0,0);

type

jl=record

x,y,dis:longint;

end;

var

map:array[0..21,0..21] of char;

can:array[0..21,0..21] of boolean;

rec:array[0..500] of jl;

mindis,n,m,i,j,l,r:longint;

find:boolean;

procedure floodfill(x1,y1,diss:longint);

var

i:longint;

begin

if not can[x1,y1] then exit;

if x1=n then

begin

if mindis>diss then mindis:=diss;

exit;

end;

inc(r);

rec[r].x:=x1;

rec[r].y:=y1;

rec[r].dis:=diss;

can[x1,y1]:=false;

for i:=1 to 4 do

if map[x1,y1]=map[x1+dx[i],y1+dy[i]] then

floodfill(x1+dx[i],y1+dy[i],diss);

end;

procedure bfs(t:longint);

var

i,j,k,x1,y1:longint;

begin

for i:=1 to n do

for j:=1 to m do

can:=true;

find:=false;

rec[1].x:=1;

rec[1].y:=t;

rec[1].dis:=1;

l:=0;

r:=1;

floodfill(1,t,1);

repeat

inc(l);

for i:=1 to 4 do

begin

x1:=rec[l].x+dx[i];

y1:=rec[l].y+dy[i];

if not can[x1,y1] then continue;

floodfill(x1,y1,rec[l].dis+1);

if find then exit;

end;

until l>=r;

end;

begin

assign(input,'meet.in');

reset(input);

assign(output,'meet.out');

rewrite(output);

for i:=1 to n do

begin

for j:=1 to m do

end;

mindis:=oo;

for i:=1 to m do

bfs(i);

writeln(mindis);

close(input);

close(output);

end.

• @ 2009-10-18 16:37:38

用图论的注意了

这题数据范围有点问题

要开450的点

• @ 2009-10-06 09:51:21

原来floodfill这么简单。。晕。

用最短路 157行O.O

• @ 2009-09-20 14:01:48

太恶心了

之前用FLOODFILL+FLOYD做的时候把边的数组开小了

交上去它竟然显示的是答案错误和输出比正确答案长！！！

太误导人了

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案错误...程序输出比正确答案长

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案错误...程序输出比正确答案长

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案错误...程序输出比正确答案长

├ 测试数据 13：答案错误...程序输出比正确答案长

├ 测试数据 14：答案错误...　├ 标准行输出

├ 错误行输出

├ 测试数据 15：答案错误...程序输出比正确答案长

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：运行时错误...|错误号: -1073741571

├ 测试数据 18：运行时错误...|错误号: -1073741571

├ 测试数据 19：答案正确... 0ms

├ 测试数据 20：运行时错误...|错误号: -1073741571

后来把[0..21,0..21]改成[0..450,0..450]就

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 0ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：答案正确... 0ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 509ms

├ 测试数据 18：答案正确... 431ms

├ 测试数据 19：答案正确... 0ms

├ 测试数据 20：答案正确... 509ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1449ms

• @ 2009-09-14 18:21:10

话说这题的还是有点委琐，看了那么长古文发现一点用都没...

解法1：BFS

这个比较简单，注意一个结点4个方向都要搜的。

解法2：最短路

先对这个图进行一次遍历，将字母相同的点缩成一个结点。

添加一个超级源，对第一行的字母添加一条权为1的边。

添加一个超级汇，最后一行添加一条权为0的边；

然后求超级源到超级汇的最短路。

不过由于此题数据极弱，DFS竟然也AC了

• @ 2009-09-13 22:32:08
• @ 2009-09-13 21:18:10

俺是小号俺怕谁？

记录编号 Flag 得分 记录信息 环境 评测机 程序提交时间

R1528771 Accepted 100 From li_－

P1406 FPC Vivid Puppy 2009-9-13 21:14:03

R1528752 Unaccepted 85 From li_－

P1406 FPC Vijos Sunny 2009-9-13 21:11:28

R1528717 Unaccepted 95 From li_－

P1406 FPC Vivid Puppy 2009-9-13 21:05:08

R1528706 Unaccepted 70 From li_－

P1406 FPC Vivid Puppy 2009-9-13 21:01:50

R1528695 Unaccepted 45 From li_－

P1406 FPC Vivid Puppy 2009-9-13 21:00:08

R1528690 No Compiled 0 From li_－

P1406 CPP Vivid Puppy 2009-9-13 20:58:57

六次，第一次选成CPP了，第五次纯属RP问题。。。。

FLOYED万岁！！！！！

ID
1406

5

(无)

1500

462

31%

2