NYOJ 迷宫寻宝(一)

# include<iostream>

# include<string>

# include<string.h>

# include<queue>

# include<stdio.h>

# include<math.h>

#include <algorithm>

using namespace std;

char d[][];

int a[],b[];

struct Node

{

    int x,y;

    int num;

}node,temp,f[];

queue<Node> q,q1;

void bfs(int x,int y,int m,int n)

{

    int k;

    node.x = x;

    node.y = y;

    q.push(node);

    d[x][y] = '';

    while(!q.empty())

    {

        temp = q.front();

        q.pop();

        for(int i=;i<;i++)

        {

            int t1,t2;

            t1 = temp.x + f[i].x;

            t2 = temp.y + f[i].y;

            if(t1< ||t1>=m || t2< || t2>=n)

                continue;

            if(d[t1][t2] == 'G')

            {

                printf("YES\n");

                return;

            }

            else if(d[t1][t2] == '' || d[t1][t2] == 'X')

            {

                continue;

            }

            else if(d[t1][t2] == 'A' || d[t1][t2] == 'B' || d[t1][t2] == 'C' || d[t1][t2] == 'D' || d[t1][t2] == 'E')

            {

                k = d[t1][t2] - 'A';

                if(b[k]>=a[k] && a[k]!=)

                {

                    d[t1][t2] = '';

                    node.x = t1;

                    node.y = t2;

                    q.push(node);

                }

                else

                {

                    node.x = t1;

                    node.y = t2;

                    node.num = k;

                    q1.push(node);

                }

            }

            else if(d[t1][t2] == '.' || d[t1][t2] == 'a' || d[t1][t2] == 'b' || d[t1][t2] == 'c' || d[t1][t2] == 'd' || d[t1][t2] == 'e')

            {

                if(d[t1][t2]!='.')

                {

                    k = d[t1][t2] - 'a';

                    b[k]++;

                }

                d[t1][t2] = '';

                node.x = t1;

                node.y = t2;

                q.push(node);

            }

        }

        if(q.empty()==true && q1.empty()!=true)

        {

            k = q1.size();

            for(int i=;i<k;i++)

            {

                temp = q1.front();

                q1.pop();

                if(b[temp.num]>=a[temp.num] && a[temp.num]!=)

                {

                    q.push(temp);

                    d[temp.x][temp.y] = '';

                }

                else

                {

                    q1.push(temp);

                }

            }

        }

    }

    //要清空q1

    while(!q1.empty())

    {

        q1.pop();

    }

    printf("NO\n");

}

int main()

{

      int n,m,i,j,x,y;

      f[].x=;f[].y=;

      f[].x=;f[].y=-;

      f[].x=;f[].y=;

      f[].x=-;f[].y=;

      scanf("%d %d",&m,&n);

      getchar();

      while(n!= || m!=)

      {

          for(i=;i<;i++)

        {

            a[i] = ;

            b[i] = ;

        }

        //要重置d数组

        for(i=;i<;i++)

            for(j=;j<;j++)

                d[i][j]='';

          for(i=;i<m;i++)

          {

              for(j=;j<n;j++)

            {

                scanf("%c",&d[i][j]);

                if(d[i][j]=='S')

                {

                    x = i;

                    y = j;

                }

                if(d[i][j]=='a')        a[]++;

                else if(d[i][j]=='b')    a[]++;

                else if(d[i][j]=='c')    a[]++;

                else if(d[i][j]=='d')    a[]++;

                else if(d[i][j]=='e')    a[]++;

            }

            getchar();

        }

        bfs(x,y,m,n);

        /*

        for(i=0;i<m;i++)

          {

              for(j=0;j<n;j++)

            {

                printf("%c",d[i][j]);

            }

            printf("\n");

        }

        */

        scanf("%d %d",&m,&n);

        //WA原因 少了这句话

        getchar();

    }

    return ;

}