第一周基础知识J - Crazy Robot

kabout · 2023-01-07 12:24:28 · 个人记录

题意： 你要把机器人赶回去，他除了你给的指令方向，其他方向都能走。

分析： 其实很简单，搜索正着肯定不太好搜，因为你不知道他往哪里走，状态肯定很多而且会tle，所以倒着搜就行了，从终点搜，然后看看走出的这一步是不是只能最多有两种选择（这样你就可以封锁一种，把他逼过来），然后可以被逼到终点的格子也算是封锁，因为你到它上面一定可以逼过来，用dfs把所有点过一遍即可。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
ll t,n,m,k,u[4][2]={1,0,0,1,-1,0,0,-1};
string mp[1000001];
//int cc[1000001];
#define TLE ios::sync_with_stdio(0),cin.tie(0)
bool check(int xk,int yk)
{
    int cnt=4;
    for(int i=0;i<4;i++)
    {
        int xi=xk+u[i][0],yi=yk+u[i][1];
        if(xi<1||xi>n||yi<1||yi>m||mp[xi][yi]=='#'||mp[xi][yi]=='+'||mp[xi][yi]=='L')cnt--;
    }
    if(cnt<2)return 1;
    return 0;
}
void dfs(int xk,int yk)
{
//  cc[(xk-1)*n+yk]++;
//  if(cc[(xk-1)*n+yk]>5)return;
    for(int i=0;i<4;i++)
    {
        int xi=xk+u[i][0],yi=yk+u[i][1];
        if(xi<1||xi>n||yi<1||yi>m||mp[xi][yi]=='+'||mp[xi][yi]=='L'||mp[xi][yi]=='#'){
            continue;
        }
        if(check(xi,yi))mp[xi][yi]='+',dfs(xi,yi);
    }
}
int main()
{
    TLE;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
//      for(int i=1;i<=n*m;i++)
    //      cc[i]=0;
        for(int i=1;i<=n;i++)
        {
            mp[i]="#";
            string tmp;
            cin>>tmp;
            mp[i]+=tmp;
        }       
        int x,y;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                if(mp[i][j]=='L'){
                    x=i,y=j;
                    break;
                }
        dfs(x,y);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
                cout<<mp[i][j];     
            cout<<"\n"; 
        }
//      cout<<"CNT: "<<cnt<<endl;

    }

    return 0;
}