2015 CCPC H문제【DFS】

2426 단어
제목
제목: 수독, 1-4로 4*4의 칸을 채우고 칸 안의 문자*는 공백을 나타낸다.
생각: DFS 폭력이면 된다.
AC 코드:
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <map>
#include <string>
#include <vector>
#define lson o<<1|1, l, mid
#define rson o<<1, mid+1, r
#define ll o<<1
#define rr o<<1|1
#define INF 0x3f3f3f3f
#define eps 1e-8
#define debug printf("1
") #define MAXN 10000 #define MAXM 100000 #define LL long long #define CLE(a, b) memset(a, (b), sizeof(a)) #define W(a) while(a--) #define Ri(a) scanf("%d", &a) #define Pi(a) printf("%d
", (a)) #define Rl(a) scanf("%lld", &a) #define Pl(a) printf("%lld
", (a)) #define Ss(a) scanf("%s", a) #define Ps(a) printf("%s
", a) using namespace std; int Map[5][5]; bool judge(int x, int y, int val) { for(int i = 0; i < 4; i++) if(Map[x][i] == val) return false; for(int i = 0; i < 4; i++) if(Map[i][y] == val) return false; int row, cul; row = x / 2 * 2; cul = y / 2 * 2; for(int i = row; i < row+2; i++) for(int j = cul; j < cul+2; j++) if(Map[i][j] == val) return false; return true; } void DFS(int x, int y) { if(x == 4) { for(int i = 0; i < 4; i++) { for(int j = 0; j < 4; j++) printf("%d", Map[i][j]); printf("
"); } } else if(y == 4) DFS(x+1, 0); else if(Map[x][y]) DFS(x, y+1); else { for(int i = 1; i <= 4; i++) { if(judge(x, y, i)) { Map[x][y] = i; DFS(x, y+1); Map[x][y] = 0; } } } } char str[5]; int main() { int t, kcase = 1; scanf("%d", &t); W(t) { getchar(); for(int i = 0; i < 4; i++) { Ss(str); for(int j = 0; j < 4; j++) { if(str[j] == '*') Map[i][j] = 0; else Map[i][j] = str[j] - '0'; } } printf("Case #%d:
", kcase++); DFS(0, 0); } return 0; }

좋은 웹페이지 즐겨찾기