[CRCI2008-2009] CIJEVI

· · 题解

题目

中模拟，爱了爱了。

分析&思路

题目中的限制很多，数据范围很小，直接乱搞。

大致分为两个部分：

  1. 首先需要知道哪里被删除了，很简单，直接从 M 开始（当然也可以从 Z 开始啦，我从 M 开始搜的，以下均按此标准）深搜，直到搜到 . 为止。搜索时要确定方向，可以设为与 M 相邻的构建块的方向。

    但是……

    如上 Hack 把被删除的地方设在了与 M 相邻的地方上，再加上题目中说：莫斯科和克罗地亚的每一个都将恰好有一个构建块。没有与 M 相邻的构建块，无法确定方向，怎么办呢？很简单，这不就相当于有多个可能被删除的地方嘛！直接枚举每个可能被删除的地方，然后进行步骤 2，这样就可以确定方向了，因为可以把可能被删除的地方看成与 M 相邻的构建块。

  2. 再暴力枚举，把被删除的地方依次替换成 7 种管道再按步骤 1 的方式在搜一遍看能否到达对方。

代码

#include <bits/stdc++.h>
using namespace std;
// 下，右，上，左
const int dx[] = {1 , 0 , -1 , 0};
const int dy[] = {0 , 1 , 0 , -1};
int r , c , mx , my , zx , zy , bx , by;
char mp[30][30] , ansc;

bool check(int x , int y) {return x >= 1 && x <= r && y >= 1 && y <= c && mp[x][y] != '.';}

int get_d(int x , int y , int d)
{
    int nd = d;
    if (mp[x][y] == '1') nd = (d == 2 ? 1 : 0);
    else if (mp[x][y] == '2') nd = (d == 0 ? 1 : 2);
    else if (mp[x][y] == '3') nd = (d == 1 ? 2 : 3);
    else if (mp[x][y] == '4') nd = (d == 1 ? 0 : 3);
    return nd;
}

void dfs1(int x , int y , int d)
{
    if (mp[x][y] == '.') {bx = x; by = y; return;}
    d = get_d(x , y , d);
    int nx = x + dx[d] , ny = y + dy[d];
    dfs1(nx , ny , d);
    return;
}

void dfs2(int x , int y , int d)
{
    if (mp[x][y] == 'Z') {printf("%d %d %c" , bx , by , mp[bx][by]); exit(0);}
    int nx = x + dx[d] , ny = y + dy[d];
    if (check(nx , ny) && 
    //看与下一个构建块是否相连
    (mp[nx][ny] == 'Z' || 
    (mp[nx][ny] == '|' && d % 2 == 0) || 
    (mp[nx][ny] == '-' && d % 2 == 1) || 
    mp[nx][ny] == '+' || 
    (mp[nx][ny] == '1' && (d == 2 || d == 3)) || 
    (mp[nx][ny] == '2' && (d == 3 || d == 0)) || 
    (mp[nx][ny] == '3' && (d == 0 || d == 1)) || 
    (mp[nx][ny] == '4' && (d == 1 || d == 2))
    )) dfs2(nx , ny , get_d(nx , ny , d));
    return;
}

int main()
{
    cin >> r >> c;
    for (int i = 1 ; i <= r ; i++)
        for (int j = 1 ; j <= c ; j++)
        {
            cin >> mp[i][j];
            if (mp[i][j] == 'M') {mx = i; my = j;}
            if (mp[i][j] == 'Z') {zx = i; zy = j;}
        }

    int mtd = -1;
    for (int i = 0 ; i < 4 ; i++)
    {
        int tx = mx + dx[i] , ty = my + dy[i];
        if (check(tx , ty)) {mtd = i; break;}
    }
    if (mtd != -1) dfs1(mx , my , mtd);

    if (mtd == -1)
    {
        for (int i = 0 ; i < 4 ; i++)
        {
            bx = mx + dx[i] , by = my + dy[i];
            if (bx >= 1 && bx <= r && by >= 1 && by <= c)
            {
                mp[bx][by] = '|';
                dfs2(mx , my , i);
                mp[bx][by] = '-';
                dfs2(mx , my , i);
                mp[bx][by] = '+';
                dfs2(mx , my , i);
                mp[bx][by] = '1';
                dfs2(mx , my , i);
                mp[bx][by] = '2';
                dfs2(mx , my , i);
                mp[bx][by] = '3';
                dfs2(mx , my , i);
                mp[bx][by] = '4';
                dfs2(mx , my , i);
            }
        }
    }
    else
    {
        mp[bx][by] = '|';
        dfs2(mx , my , mtd);
        mp[bx][by] = '-';
        dfs2(mx , my , mtd);
        mp[bx][by] = '+';
        dfs2(mx , my , mtd);
        mp[bx][by] = '1';
        dfs2(mx , my , mtd);
        mp[bx][by] = '2';
        dfs2(mx , my , mtd);
        mp[bx][by] = '3';
        dfs2(mx , my , mtd);
        mp[bx][by] = '4';
        dfs2(mx , my , mtd);
    }
    return 0;
}