team2012-F3-sol-0013

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
题意：给定一个n*m的矩形场地，场地中有一些守卫，守卫按顺时针方向向四周巡视，每个时刻只看一个方向并有视野长度。
问从起点到终点最少被守卫看多少次，在此情况下最少时间是多少。
解法：将两个点之间的“距离”视为一个pair<被看到多少次，时间>，在这个4层的图上求起点到终点的最短路即可。
}}}
{{{
#include <iostream>
#include <cstdio>
#include <cstring>
#include <utility>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int MAXN = 102;
const int INFI = 2100000000;
bool mp[MAXN][MAXN];
int n, m, s;
int st_x, st_y, end_x, end_y,
    def[MAXN][MAXN][4];
PII dis[MAXN][MAXN][4];
bool inq[MAXN][MAXN][4];

struct ele
{
    int x, y, t;
};
queue<ele> q;

int dir[4][2] = {
{0, 1}, {1, 0}, {0, -1}, {-1, 0}
};

bool check(int x, int y)
{
    return (x && y && x<=n && y<=m);
}

int getdir(char ch)
{
    if(ch == 'E')   return 0;
    if(ch == 'S')   return 1;
    if(ch == 'W')   return 2;
    if(ch == 'N')   return 3;
}

int nextdir(int d)
{
    return (d+1) % 4;
}

void gao()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            for(int k=0;k<4;k++)
                dis[i][j][k].first = dis[i][j][k].second = INFI;
    dis[st_x][st_y][0].first = def[st_x][st_y][0];
    dis[st_x][st_y][0].second = 0;

    while(!q.empty())   q.pop();
    memset(inq, 0, sizeof(inq));
    ele start = {st_x, st_y, 0};
    q.push(start);
    while(!q.empty())
    {
        ele now = q.front();
        q.pop();
        inq[now.x][now.y][now.t] = 0;

        for(int i=0;i<4;i++)
        {
            ele next = {now.x + dir[i][0], now.y + dir[i][1], (now.t+1) % 4};
            if(!check(next.x, next.y))
                continue;
            if(mp[next.x][next.y] == 0)
            {
                PII a = make_pair(
                        dis[now.x][now.y][now.t].first+def[next.x][next.y][next.t],
                        dis[now.x][now.y][now.t].second+1);
                if(a < dis[next.x][next.y][next.t])
                {
                    dis[next.x][next.y][next.t] = a;
                    q.push(next);
                    inq[next.x][next.y][next.t] = 1;
                }
            }
        }
    }
}

int main()
{
    while(~scanf("%d %d %d", &n, &m, &s))
    {
        memset(mp, 0, sizeof(mp));
        for(int i=1;i<=n;i++)
        {
            getchar();
            for(int j=1;j<=m;j++)
            {
                char ch;
                scanf("%c", &ch);
                if(ch == '*')
                    mp[i][j] = 1;
            }
        }

        memset(def, 0, sizeof(def));
        for(int i=1;i<=s;i++)
        {
            int x, y, l;
            char d;
            scanf("%d %d %d %c", &x, &y, &l, &d);
            mp[x][y] = 1;
            int dr = getdir(d);
            for(int j=0;j<4;j++, dr = nextdir(dr))
            {
                int tx = x, ty = y;
                for(int p=1;p<=l;p++)
                {
                    tx += dir[dr][0];
                    ty += dir[dr][1];
                    if(!check(tx, ty))
                        break;
                    def[tx][ty][j]++;
                }
            }
        }

        scanf("%d %d %d %d", &st_x, &st_y, &end_x, &end_y);
        gao();

        PII ans = make_pair(INFI, INFI);
        for(int i=0;i<4;i++)
            if(dis[end_x][end_y][i] < ans)
                ans = dis[end_x][end_y][i];
        if(ans.first != INFI)
            cout<<ans.first<<' '<<ans.second<<endl;
        else
            cout<<-1<<endl;
    }
    return 0;
}
}}}

题意：给定一个n*m的矩形场地，场地中有一些守卫，守卫按顺时针方向向四周巡视，每个时刻只看一个方向并有视野长度。
问从起点到终点最少被守卫看多少次，在此情况下最少时间是多少。
解法：将两个点之间的“距离”视为一个pair<被看到多少次，时间>，在这个4层的图上求起点到终点的最短路即可。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <utility>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int MAXN = 102;
const int INFI = 2100000000;
bool mp[MAXN][MAXN];
int n, m, s;
int st_x, st_y, end_x, end_y,
    def[MAXN][MAXN][4];
PII dis[MAXN][MAXN][4];
bool inq[MAXN][MAXN][4];
struct ele
{
    int x, y, t;
};
queue<ele> q;
int dir[4][2] = {
{0, 1}, {1, 0}, {0, -1}, {-1, 0}
};
bool check(int x, int y)
{
    return (x && y && x<=n && y<=m);
}
int getdir(char ch)
{
    if(ch == 'E')   return 0;
    if(ch == 'S')   return 1;
    if(ch == 'W')   return 2;
    if(ch == 'N')   return 3;
}
int nextdir(int d)
{
    return (d+1) % 4;
}
void gao()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            for(int k=0;k<4;k++)
                dis[i][j][k].first = dis[i][j][k].second = INFI;
    dis[st_x][st_y][0].first = def[st_x][st_y][0];
    dis[st_x][st_y][0].second = 0;
    while(!q.empty())   q.pop();
    memset(inq, 0, sizeof(inq));
    ele start = {st_x, st_y, 0};
    q.push(start);
    while(!q.empty())
    {
        ele now = q.front();
        q.pop();
        inq[now.x][now.y][now.t] = 0;
        for(int i=0;i<4;i++)
        {
            ele next = {now.x + dir[i][0], now.y + dir[i][1], (now.t+1) % 4};
            if(!check(next.x, next.y))
                continue;
            if(mp[next.x][next.y] == 0)
            {
                PII a = make_pair(
                        dis[now.x][now.y][now.t].first+def[next.x][next.y][next.t],
                        dis[now.x][now.y][now.t].second+1);
                if(a < dis[next.x][next.y][next.t])
                {
                    dis[next.x][next.y][next.t] = a;
                    q.push(next);
                    inq[next.x][next.y][next.t] = 1;
                }
            }
        }
    }
}
int main()
{
    while(~scanf("%d %d %d", &n, &m, &s))
    {
        memset(mp, 0, sizeof(mp));
        for(int i=1;i<=n;i++)
        {
            getchar();
            for(int j=1;j<=m;j++)
            {
                char ch;
                scanf("%c", &ch);
                if(ch == '*')
                    mp[i][j] = 1;
            }
        }
        memset(def, 0, sizeof(def));
        for(int i=1;i<=s;i++)
        {
            int x, y, l;
            char d;
            scanf("%d %d %d %c", &x, &y, &l, &d);
            mp[x][y] = 1;
            int dr = getdir(d);
            for(int j=0;j<4;j++, dr = nextdir(dr))
            {
                int tx = x, ty = y;
                for(int p=1;p<=l;p++)
                {
                    tx += dir[dr][0];
                    ty += dir[dr][1];
                    if(!check(tx, ty))
                        break;
                    def[tx][ty][j]++;
                }
            }
        }
        scanf("%d %d %d %d", &st_x, &st_y, &end_x, &end_y);
        gao();
        PII ans = make_pair(INFI, INFI);
        for(int i=0;i<4;i++)
            if(dis[end_x][end_y][i] < ans)
                ans = dis[end_x][end_y][i];
        if(ans.first != INFI)
            cout<<ans.first<<' '<<ans.second<<endl;
        else
            cout<<-1<<endl;
    }
    return 0;
}