Codeforces 510B Fox And Two Dots 【DFS】

好久好久，都没有写过搜索了，看了下最近在CF上有一道DFS水题 = =

数据量很小，爆搜一下也可以过

额外注意的就是防止往回搜索需要做一个判断。

Source code:

//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler

#include <bits/stdc++.h>

#define Max(a,b) (((a) > (b)) ? (a) : (b))

#define Min(a,b) (((a) < (b)) ? (a) : (b))

#define Abs(x) (((x) > 0) ? (x) : (-(x)))

#define MOD 1000000007

#define pi acos(-1.0)

using namespace std;

typedef long long           ll      ;

typedef unsigned long long  ull     ;

typedef unsigned int        uint    ;

typedef unsigned char       uchar   ;

template<class T> inline void checkmin(T &a,T b){if(a>b) a=b;}

template<class T> inline void checkmax(T &a,T b){if(a<b) a=b;}

const double eps = 1e-      ;

const int N =               ;

const int M =          ;

const ll P = 10000000097ll   ;

const int INF = 0x3f3f3f3f   ;

char mp [][];

int n,m;

int Dir [][] = {{,},{,},{-,},{,-}};

int Vis [][];

int Fit(int x , int y){

    return x >=  && x < n && y >=  && y < m;

}

int Dfs (int x, int y, int px, int py, char c){

    Vis[x][y] = ;

    for(int i =  ; i <  ; ++i){

        int dx = x + Dir[i][];

        int dy = y + Dir[i][];

        if(dx == px && dy == py)    continue;

        if (Fit (dx , dy) && mp[dx][dy] == c){

            if (Vis[dx][dy]){

                return ;

            }

            if (Dfs (dx ,dy, x, y, mp[dx][dy])){

                return ;

            }

        }

    }

    return ;

}

int main(){

    int i ,j ;

    while(cin >> n >> m){

        memset(Vis, , sizeof(Vis));

        for(i = ; i < n; ++i){

            for(j = ; j < m; ++j){

                cin >> mp[i][j];

            }

        }

        for(i = ; i < n; ++i){

            for(j = ; j < m; ++j){

                if(!Vis[i][j]){

                    if(Dfs(i, j, -, -, mp[i][j])){

                        cout << "Yes" << endl;

                        return ;

                    }

                }

            }

        }

        cout << "No" << endl;

    }

    return ;

}