89 条题解

  • 4
    @ 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.

  • 1
    @ 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;
    }
    
  • 1
    @ 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]){
        adjm[fill][blockid[y][x]] = true;
        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++){
        adjm[ST][blockid[1][j]] = adjm[blockid[1][j]][ST] = true;
        adjm[ED][blockid[m][j]] = adjm[blockid[m][j]][ED] = true;
      }
    
      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++){
          if(adjm[node][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
    
  • 0
    @ 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;
    }
    
  • 0
    @ 2018-04-16 21:47:02

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

  • 0
    @ 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;
    }
    
  • 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;
    }
    
  • 0
    @ 2015-01-29 19:01:22

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

  • 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]

  • 0
    @ 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

    readln(m,n);

    for i:=1 to m do begin

    for j:=1 to n do read(a);readln;end;

    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

  • 0
    @ 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

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

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

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

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

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

    后来用floyd超爆...

    最后,

    floodfill预处理+spfa

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

  • 0
    @ 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

    //MADE BY AYZK

    //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);

    readln(n,m);

    for i:=1 to n do

    begin

    for j:=1 to m do

    read(map);

    readln;

    end;

    mindis:=oo;

    for i:=1 to m do

    bfs(i);

    writeln(mindis);

    close(input);

    close(output);

    end.

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

    用图论的注意了

    这题数据范围有点问题

    要开450的点

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

    原来floodfill这么简单。。晕。

    用最短路 157行O.O

  • 0
    @ 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

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

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

    解法1:BFS

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

    解法2:最短路

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

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

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

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

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

  • 0
    @ 2009-09-13 22:32:08

    楼上的是俺的小号。。。。

    题解:

    http://lifeich1.spaces.live.com/blog/cns!9AB465A9D807BE22!190.entry

  • 0
    @ 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
上传者