HDOJ 4308 Saving Princess claire_

简单BFS，遇到'P'时把所有'P'标记，并对所有'P'多向下搜索一步，此时遇到'*'时入队；

BFS的特点：搜到即标记，搜到就判断。

# include <cstdio>
# include <cstring>
# include <queue>

using namespace std;

# define N 5000+5

int n, m, cost;
char g[N][N];
char vis[N][N];

struct pos
{
    int x, y, d;
    pos()
    {
        d = 0;
    }
};
pos st;
queue <pos> Qst;

const int dx[] = {0,0,1,-1};
const int dy[] = {1,-1,0,0};

int bfs(void)
{
    queue <pos> Q;
    Q.push(st);
    vis[st.x][st.y] = 1;
    while (!Q.empty())
    {
        pos cur = Q.front(); Q.pop();
        for (int i = 0; i < 4; ++i)
        {
            pos nst;
            nst.x = cur.x + dx[i];
            nst.y = cur.y + dy[i];
            if (1<=nst.x&&nst.x<=n && 1<=nst.y&&nst.y<=m && !vis[nst.x][nst.y])
            {
                vis[nst.x][nst.y] = 1;
                if (g[nst.x][nst.y] == 'C') return cur.d;
                if (g[nst.x][nst.y] == '#') continue;
                if (g[nst.x][nst.y] == '*') nst.d=cur.d+1,Q.push(nst);
                else if (g[nst.x][nst.y] == 'P')
                {
                    while (!Qst.empty())
                    {
                        nst = Qst.front(); Qst.pop();
                        vis[nst.x][nst.y] = 1;
                        for (int j = 0; j < 4; ++j)
                        {
                            pos pst;
                            pst.x = nst.x + dx[j];
                            pst.y = nst.y + dy[j];
                            if (1<=pst.x&&pst.x<=n && 1<=pst.y&&pst.y<=m && !vis[pst.x][pst.y])
                            {
                                vis[pst.x][pst.y] = 1;
                                if (g[pst.x][pst.y] == 'C') return cur.d;
                                if (g[pst.x][pst.y] == '#') continue;
                                if (g[pst.x][pst.y] == '*') pst.d = cur.d+1, Q.push(pst);
                            }
                        }    
                    }
                }
            }
        }
    }
    return -1;
}

void read(void)
{
    pos tmp;
    while (!Qst.empty()) Qst.pop();
    for (int i = 1; i <= n; ++i)
    {
        scanf("%s", g[i]+1);
        memset(vis[i]+1, 0, sizeof(char)*m);
        for (int j = 1; j <= m; ++j)
        {
            if (g[i][j] == 'P')
            {
                tmp.x = i, tmp.y = j;
                Qst.push(tmp);
             }
             else if (g[i][j] == 'Y')
             {
                 st.x = i, st.y = j;
                 st.d = 0;
              }
         }
     }
}

void solve(void)
{
    int ans = bfs();
    if (ans == -1)
        puts("Damn teoy!");
    else
        printf("%d\n", ans*cost);
}

int main()
{
    while (~scanf("%d%d%d", &n, &m, &cost))
    {
        read();
        solve();
    }
    
    return 0;
}

/**/