HDU 2612Find a way（杭电acm）求指点迷津

码拜

8年 ago

一直提交全是WA…

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <queue>
using namespace std;
struct p{
int x,y,step;
}now,nex;
int n,sx,sy,dx,dy,m,sum[205][205],vis[205][205];
char pla[205][205];
int fangxiang[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
void bfs(int x,int y)
{
    queue<p>q;
    now.x=x;
    now.y=y;
    now.step=0;
    vis[now.x][now.y]=1;
    q.push(now);
    while(!q.empty())
    {
        now=q.front();
        q.pop();
        nex=now;
        for(int i=0;i<4;i++)
        {
            nex.x=now.x+fangxiang[i][0];
            nex.y=now.y+fangxiang[i][1];
            if(pla[nex.x][nex.y]!=”#”&&nex.x>=0&&nex.x<n&&nex.y>=0&&nex.y<m&&!vis[nex.x][nex.y])
            {
                if(pla[nex.x][nex.y]==”@”)
                {
                    nex.step=now.step+1;
                    vis[nex.x][nex.y]=1;
                    sum[nex.x][nex.y]=sum[nex.x][nex.y]+nex.step;//printf(“%d  %d  %d %d \n”,nex.x,nex.y,sum[nex.x][nex.y],o);
                    q.push(nex);
                }
                else
                {
                    nex.step=now.step+1;
                    vis[nex.x][nex.y]=1;
                    q.push(nex);
                }
            }
        }
    }
}
int main()
{
    while(scanf(“%d %d”,&n,&m)!=EOF)
    {
        int i,g=999999,k[40000][2];
        getchar();
        memset(sum,0,sizeof(sum));
        int l=0;
        for(i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                scanf(“%c”,&pla[i][j]);
                if(pla[i][j]==”Y”)
                {
                    sx=i;
                    sy=j;
                }
                if(pla[i][j]==”M”)
                {
                    dx=i;
                    dy=j;
                }
                if(pla[i][j]==”@”)
                {
                    k[l][0]=i;
                    k[l][1]=j;
                    l++;
                }
            }
            getchar();
        }
        memset(vis,0,sizeof(vis));
        bfs(sx,sy);
        memset(vis,0,sizeof(vis));
        bfs(dx,dy);
        for(i=0;i<l;i++)
        {
           //printf(“%d\n”,l);
            if(g>sum[k[i][0]][k[i][1]])
                g=sum[k[i][0]][k[i][1]];
        }
        printf(“%d\n”,g*11);
    }
    return 0;
}
新手求指点，谢谢。

解决方案

LZ程序对以下输入的计算结果是0：
4 4
YM#@
…#
….
…@
错误原因是位于[0,3]的@实际是不能达到的，但由于sum被初始化为全0，因此最后取到的最小值是0。
如下修改可AC：

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <queue>
using namespace std;
struct p{
  int x,y,step;
}now,nex;
int n,sx,sy,dx,dy,m,sum[205][205][2],vis[205][205];//改 int n,sx,sy,dx,dy,m,sum[205][205],vis[205][205];
char pla[205][205];
int fangxiang[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
void bfs(int x,int y,int k)//改 void bfs(int x,int y)
{
  queue<p>q;
  now.x=x;
  now.y=y;
  now.step=0;
  vis[now.x][now.y]=1;
  q.push(now);
  while(!q.empty())
  {
    now=q.front();
    q.pop();
    nex=now;
    for(int i=0;i<4;i++)
    {
      nex.x=now.x+fangxiang[i][0];
      nex.y=now.y+fangxiang[i][1];
      if(pla[nex.x][nex.y]!="#"&&nex.x>=0&&nex.x<n&&nex.y>=0&&nex.y<m&&!vis[nex.x][nex.y])
      {
        if(pla[nex.x][nex.y]=="@")
        {
          nex.step=now.step+1;
          vis[nex.x][nex.y]=1;
          sum[nex.x][nex.y][k]=nex.step; //改 sum[nex.x][nex.y]=sum[nex.x][nex.y]+nex.step;//printf("%d  %d  %d %d \n",nex.x,nex.y,sum[nex.x][nex.y],o);
          q.push(nex);
        }
        else
        {
          nex.step=now.step+1;
          vis[nex.x][nex.y]=1;
          q.push(nex);
        }
      }
    }
  }
}
int main()
{
  while(scanf("%d %d",&n,&m)!=EOF)
  {
    int i,g=999999,k[40000][2];
    getchar();    
    for(i=0;i<n;i++)for(int j=0;j<m;j++)for(int k=0;k<2;k++)sum[i][j][k]=g; //改 memset(sum,0,sizeof(sum));
    int l=0;
    for(i=0;i<n;i++)
    {
      for(int j=0;j<m;j++)
      {
        scanf("%c",&pla[i][j]);
        if(pla[i][j]=="Y")
        {
          sx=i;
          sy=j;
        }
        if(pla[i][j]=="M")
        {
          dx=i;
          dy=j;
        }
        if(pla[i][j]=="@")
        {
          k[l][0]=i;
          k[l][1]=j;
          l++;
        }
      }
      getchar();
    }
    memset(vis,0,sizeof(vis));
    bfs(sx,sy,0);//bfs(sx,sy);
    memset(vis,0,sizeof(vis));
    bfs(dx,dy,1);//bfs(dx,dy);
    for(i=0;i<l;i++)
    {
      //printf("%d\n",l);
      if(g>(sum[k[i][0]][k[i][1]][0] + sum[k[i][0]][k[i][1]][1])) //改 if(g>sum[k[i][0]][k[i][1]])
        g=sum[k[i][0]][k[i][1]][0] + sum[k[i][0]][k[i][1]][1]; //改 g=sum[k[i][0]][k[i][1]];
    }
    printf("%d\n",g*11);
  }
  return 0;
}

#2改得太多了。实际上只要把以下一行：
if(g>sum[k[i][0]][k[i][1]])
改为：
if(g>sum[k[i][0]][k[i][1]] && sum[k[i][0]][k[i][1]]>0)
就可以了。