LA 3790 Overlapping Squares DFS

题意：

给出一个字符矩阵，问能否是不超过6个2×2的正方形组成的。

分析：

每次找一个最表面的正方形然后DFS就好了。

一个正方形被移开后，用一个特殊符号标记上，下次再匹配的时候就直接忽略这些位置。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <string>

using namespace std;

char square[10][10] = {

    " _ _ ",

    "|   |",

    "|_ _|"

};

struct Graph

{

    string g[5];

    bool Read() {

        getline(cin, g[0]);

        if(g[0][0] == '0') return false;

        for(int i = 1; i < 5; i++) getline(cin, g[i]);

        return true;

    }

    void print() {

        for(int i = 0; i < 5; i++) cout << g[i] << endl;

    }

    bool Remove(int x, int y) {

        for(int i = 0; i < 3; i++)

            for(int j = 0; j < 5; j++) {

                if(i == 0 && (j == 0 || j == 2 || j == 4)) continue;

                if(g[x+i][y+j] == square[i][j]) g[x+i][y+j] = '*';

                else if(g[x+i][y+j] != '*') return false;

            }

        return true;

    }

    bool check() {

        for(int i = 0; i < 5; i++)

            for(int j = 0; j < 9; j++)

                if(g[i][j] != '*' && g[i][j] != ' ')

                    return false;

        return true;

    }

}G[10];

bool DFS(int d) {

    if(G[d].check()) return true;

    if(d == 6) return false;

    for(int i = 0; i <= 2; i++)

        for(int j = 0; j <= 4; j++) {

            G[d+1] = G[d];

            if(G[d+1].Remove(i, j))

                if(DFS(d+1)) return true;

        }

    return false;

}

int main()

{

    //freopen("in.txt", "r", stdin);

    int kase = 1;

    while(G[0].Read()) {

        printf("Case %d: %s\n", kase++, DFS(0) ? "Yes" : "No");

    }

    return 0;

}

巴特西

LA 3790 Overlapping Squares DFS

题意：

分析：

最新文章

热门文章