mydcwfy's Blog

P7225

Posted on
Symbols count in article: 3.4k Reading time ≈ 7 mins.

极为简单的交互题目。

1. 题意

你站在一个格子，你可以移动到相邻的格子（如果相邻的格子不是障碍物的话）。

现在你需要回答走能走到的格子有哪些。

2. 关于交互题

请确保你知道交互题的评测方式与做法。

其实，大概的意思就是你和另外一个程序同时运行，并交换数据。

本蒟蒻由于没做过几道交互题，只能讲到这个地步啦。

3. 本题

主要有两种思路：bfs 和 dfs。

注意观察 bfs 的性质：他是走到一个位置后，一会在进行扩展。

但是，本题中，我们希望的是他走的时候，是连续的，并且有回溯过程。

看到原题，他只会给你当前格子的信息，不会给你其他格子的。

所以，我们采用 dfs 进行搜索，并时刻记录有没有被访问。

由于每一个格子访问次数是常数，所以复杂度为 $O(n^2)$。

4.AC 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<bits/stdc++.h>
#define PII pair<int,int>
#define mp make_pair
#define get(i,j) (i-1)*n+j-1
#define check(i,j) (i>1&&j>1&&i<n&&j<n&&m[i][j]==-1)
using namespace std;

bool vis[705][705];
int dx[4]={1,0,0,-1},dy[4]={0,1,-1,0},n,m[705][705];
char op[4]={'S','D','A','W'};
string ans;
extern "C" bool move_to(char position);

void dfs(int x,int y)
{
    for (int i=0;i<4;++i)
    {
        if (check(x+dx[i],y+dy[i]))
        {
            if (move_to(op[i])) m[x+dx[i]][y+dy[i]]=0,dfs(x+dx[i],y+dy[i]),move_to(op[3-i]);
            else m[x+dx[i]][y+dy[i]]=1;
        }
    }  
}

extern "C" string find_out_map(int x,int y,int N){
    ans="";n=N;
    memset(m,-1,sizeof m);
    dfs(x,y);
    ans="";m[x][y]=0;
    for (int i=1;i<=n;++i)
        for (int j=1;j<=n;++j)
            if (m[i][j]==0) ans+='0';
            else ans+='1';
    return ans;
}

5. 半个交互库

我自己做的时候，由于没有交互库，无法得知自己是否正确。

自己手写的代码，算半个交互库，希望对你有所帮助。

（同时是本题的非交互写法）。

也增添了评测。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define PII pair<int,int>
#define mp make_pair
#define get(i,j) (i-1)*n+j-1
#define check(i,j) (i>1&&j>1&&i<n&&j<n&&m[i][j]==-1)
using namespace std;

const int N=705;

bool vis[N][N];
int dx[4]={1,0,0,-1},dy[4]={0,1,-1,0},n,m[N][N],nowx,nowy;
char op[4]={'S','D','A','W'};
int ansmap[N][N],tot;
string ans,stdans;

bool move_to(char position){
    if (++tot>=5e5)
    {
        puts("Too many operations!");
        exit(0);
    }
    if (position=='S'){
        if (!ansmap[nowx+1][nowy])
        {
            nowx++;
            return true;
        }
        return false;
    }
    if (position=='A'){
        if (!ansmap[nowx][nowy-1])
        {
            nowy--;
            return true;
        }
        return false;
    }
    if (position=='W'){
        if (!ansmap[nowx-1][nowy])
        {
            nowx--;
            return true;
        }
        return false;
    }
    if (position=='D'){
        if (!ansmap[nowx][nowy+1])
        {
            nowy++;
            return true;
        }
        return false;
    }
    return false;
}

void dfs(int x,int y)
{
    for (int i=0;i<4;++i)
    {
        if (check(x+dx[i],y+dy[i]))
        {
            if (move_to(op[i])) m[x+dx[i]][y+dy[i]]=0,dfs(x+dx[i],y+dy[i]),move_to(op[3-i]);
            else m[x+dx[i]][y+dy[i]]=1;
        }
    }
}

string find_out_map(int x,int y,int N)
{
    /*put your code here
      this is mine*/
    ans="";n=N;
    memset(m,-1,sizeof m);
    dfs(x,y);
    ans="";m[x][y]=0;
    for (int i=1;i<=n;++i)
        for (int j=1;j<=n;++j)
            if (m[i][j]==0) ans+='0';
            else ans+='1';
    return ans;
}

int main()
{
    cin>>nowx>>nowy>>n;
    cin>>stdans;
    for (int i=1;i<=n;++i)
        for (int j=1;j<=n;++j)
            if (stdans[get(i,j)]!='0') ansmap[i][j]=1;
            else ansmap[i][j]=0;
    //put in the stdmap
    
    if (find_out_map(nowx,nowy,n)==stdans) puts("Accepted.");
    else puts("Wrong Answer!");
    return 0;
}