当前位置：网站首页>DFS parity pruning

DFS parity pruning

2022-04-23 01:25:00 【OldLeft】

Insert picture description here
Ideas ：
Insert picture description here
Insert picture description here
Code ：

#include <iostream>
using namespace std;
const int N = 10;
int n, m, T;
char mat[N][N];
bool vis[N][N];
int dx[4]={
    0,0,-1,1};
int dy[4]={
    1,-1,0,0};
bool ok;
void dfs(int x,int y,int t){
    
    if(ok) return;
    if(t==T){
    
        if(mat[x][y]=='D') ok=true;
        return;
    }
    vis[x][y]=true;
    for(int i=0;i<4;i++){
    
        int tx=x+dx[i];
        int ty=y+dy[i];
        if(tx<0||tx>=n||ty<0||ty>=m||mat[tx][ty]=='X'||vis[tx][ty])
            continue;
        dfs(tx,ty,t+1);
    }
    vis[x][y]=false;
}
int main() {
    
    cin >> n >> m >> T;
    for (int i = 0; i < n; ++i) {
    
        cin >> mat[i];
    }
	int sx,sy,ex,ey;
    for(int i=0;i<n;i++){
    
        for(int j=0;j<m;j++){
    
            if(mat[i][j]=='S') sx=i,sy=j;
            if(mat[i][j]=='D') ex=i,ey=j;
        }
    }
    if((sx+sy+ex+ey+T)%2!=0){
    // Parity pruning 
        cout<<"NO"<<endl;
    }else{
    
        ok=false;
        dfs(sx,sy,0);
        if(ok)
            cout<<"YES"<<endl;
        else
           cout<<"NO"<<endl; 
    }
    return 0;
}

版权声明
本文为[OldLeft]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/04/202204230120462331.html

边栏推荐

猜你喜欢

随机推荐