정올 1457(백트래킹), 1824(백트래킹)

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=729&sca=3030

앞에서 푼 백트래킹문제들과 크게 다를게 없다. 기본적인 처리만 조금 더 귀찮아졌고 큰 차이는 없다.

# -*- encoding: cp949 -*-
def divide(i,j):
    if i<0 or j<0 or i>=m or j>=n:
        return
    if maps[i][j]==0:
        maps[i][j] = count
    if i+1<m and maps[i+1][j]==0:
        divide(i+1,j)
    if i-1>=0 and maps[i-1][j]==0:
        divide(i-1,j)
    if j+1<n and maps[i][j+1]==0:
        divide(i,j+1)
    if j-1>=0 and maps[i][j-1]==0:
        divide(i,j-1)

m,n,k = map(int,raw_input().split())
maps = [[0 for j in range(n)] for i in range(m)]
for i in range(k):
    x1,y1,x2,y2 = map(int,raw_input().split())
    for j in range(y1,y2):
        for k in range(x1,x2):
            maps[j][k] = -1

count = 0
for i in range(m):
    for j in range(n):
        if maps[i][j]==0:
            count += 1
            divide(i,j)
count = {}
for i in range(m):
    for j in range(n):
        if maps[i][j]!=-1:
            if maps[i][j] not in count:
                count[maps[i][j]] = 1
            else: count[maps[i][j]] += 1
count = sorted(count.itervalues())
print len(count),'\n',' '.join(map(str,count))

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1097&sca=3030

스도쿠 구하는 문제인데 시간 초과가 난다.....

# -*- encoding: cp949 -*-
import copy
import sys
sys.setrecursionlimit(100000)
global_end_flag = False

def check(row,col,t_sudoku):
    global global_end_flag
    if global_end_flag: return

    for n in xrange(1,10):
        flag = True
        for i in xrange(9):
            if t_sudoku[row][i]==n or t_sudoku[i][col]==n:
                flag = False
                break
        if not flag: 
            continue
 
        r = int(row/3)*3; c = int(col/3)*3
        for i in xrange(r,r+3):
            for j in xrange(c,c+3):
                if t_sudoku[i][j]==n:
                    flag = False
                    break
            if not flag: break
        if not flag: 
            continue

        t_sudoku[row][col] = n
        flag = False
        for i in xrange(9):
            for j in xrange(9):
                if t_sudoku[i][j]==0:
                    check(i,j,copy.deepcopy(t_sudoku))
                    flag = True
                    break
            if flag: break

    end_flag = True
    for i in xrange(9):
        for j in xrange(9):
            if t_sudoku[i][j]==0:
                end_flag = False
                break
        if not end_flag: break
    if end_flag:
        print '\n'.join(map(lambda x:' '.join(map(str,x)),t_sudoku))
        global_end_flag = True

 
sudoku = [map(int,raw_input().split()) for i in xrange(9)]
flag = False
for row in xrange(9):
    for col in xrange(9):
        if sudoku[row][col]==0:
            check(row,col,sudoku)
            flag = True
            break
    if flag: break

#print '\n'.join(map(lambda x:' '.join(map(str,x)),sudoku))