现在的位置: 首页 > 综合 > 正文

3406: [Usaco2009 Oct]Invasion of the Milkweed 乳草的入侵

2018年04月25日 ⁄ 综合 ⁄ 共 669字 ⁄ 字号 评论关闭
#include<cstdio>
#include<iostream>
using namespace std;
int n,m,bx,by;
bool mp[101][101];
int xx[8]={1,-1,1,-1,0,0,1,-1},yy[8]={1,-1,-1,1,1,-1,0,0};
struct data{
       int x,y,step;
       }q[10001];
bool judge(int x,int y)
{
     if(mp[x][y]||x<1||y<1||x>m||y>n)return 0;
     mp[x][y]=1;
     return 1;
     }
int search(int bx,int by)
{
    int t=0,w=1;
    int nowx,nowy;
    q[0].x=bx;q[0].y=by;
    mp[bx][by]=1;
    while(t<w)
    {
              for(int i=0;i<8;i++)
              {
                   nowx=q[t].x+xx[i];
                   nowy=q[t].y+yy[i];
                   if(judge(nowx,nowy))
                      {q[w].x=nowx;q[w].y=nowy;q[w].step=q[t].step+1;w++;}
                      }
              t++;
              }
    printf("%d",q[w-1].step);
    }
int main()
{
    scanf("%d%d%d%d",&n,&m,&bx,&by);//m行n列 
    char ch[101];
    for(int i=m;i>0;i--)
    {
            scanf("%s",ch);
            for(int j=0;j<n;j++)
               if(ch[j]=='*')mp[i][j+1]=1;
            }
    search(by,bx);
    return 0;
    }

抱歉!评论已关闭.