2018年东北农业大学春季校赛-wyh的吃鸡

Cwolf9 2018-04-05 原文

2018年东北农业大学春季校赛-wyh的吃鸡

BFS:

1. 从起点开始BFS，遇到X点则return；

2. vis[px][py][0]代表经过pxpy这点前还没有找到车；

　vis[px][py][1]代表经过pxpy这点前已经找到车；

3. ip记录是否找到车；

　d表示方向

4. 最后判断时间是否超时；

5. 简单的BFS，结束！

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<string>
#include<cmath>
#define test printf("***\n")
#define ka getchar();getchar()
#define ka1 getchar()
#define iis std::ios::sync_with_stdio(false)
using namespace std;
typedef long long LL;
const int N = 110;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-8;
struct lp {
    int x, y,d,ip,step;
    friend bool operator <(const lp &a,const lp &b){
        if(a.step!=b.step)return a.step>b.step;
        return a.ip<b.ip;
    }
} now, t;
int n, k;
char ar[N][N];
int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
bool vis[N][N][10];
int bfs(int a, int b)
{
    priority_queue<lp>Q;
    memset(vis,0,sizeof(vis));
    t.x = a; t.y = b;
    t.d = -1;t.ip=0;
    t.step=0;
    Q.push(t);
    vis[a][b][0]=1;
    while(!Q.empty()) {
        t = Q.top(); Q.pop();
        for(int i = 0; i < 4; ++i) {
            int px = t.x + dir[i][0], py = dir[i][1] + t.y;
            if(px < 0 || py < 0 || px >= n || py >= n)continue;
            if(ar[px][py] == 'O')continue;
            if(t.step>k)return 0;
            if(t.ip == 0) {
                if(vis[px][py][0])continue;
                if(t.d != -1 && t.d != i)continue;
                if(t.d != -1) {
                    now.d = -1;now.ip=0;
                    now.x = px; now.y = py;
                    vis[px][py][0]=1;
                    now.step = t.step + 1;
                    if(ar[px][py]=='X')return now.step;
                    if(ar[px][py]=='C'){
                        now.ip=1;
                        vis[px][py][1]=1;
                    }
                    Q.push(now);
                } else {
                    now.d = i;now.ip=0;
                    now.x = t.x; now.y = t.y;
                    now.step = t.step + 1;
                    Q.push(now);
                }
            }else{
                if(vis[px][py][1])continue;
                now.d = i;now.ip=1;
                now.x = px; now.y = py;
                now.step = t.step + 1;
                if(ar[px][py]=='X')return now.step;
                vis[px][py][1]=1;
                Q.push(now);
            }
        }
    }
    return 0;
}
int main()
{
    int t;
    scanf("%d", &t);
    while(t--) {
        int a, b;
        scanf("%d%d", &n, &k);
        for(int i = 0; i < n; ++i) {
            scanf("%s", &ar[i]);
            for(int j = 0; j < n; ++j) {
                if(ar[i][j] == 'S')a = i, b = j;
            }
        }
        int ans = bfs(a, b);
        if(ans!=0&&ans<=k) {
            printf("YES\n%d\n", ans);
        } else {
            printf("NO\n");
        }
    }
    return 0;
}
/*
3
2 3
.X
S.
2 3
.X
SC
2 4
.X
S.
*/