글 읽기 - 반례좀 찾아주세요 ㅠㅠ

dayo05 3년 전 0

반례좀 찾아주세요 ㅠㅠ

C#이긴 한데 다른 언어랑 큰 차이가 없어서 알고리즘쪽만 좀 봐주세요 ㅠㅠ

using System;
using System.Collections.Generic;
using System.IO;

namespace ConsoleApp4
{ 
    class xypos
    {
        public int x = 0;
        public int y = 0;
        public xypos(int a,int b)
        {
            x = a;
            y = b;
        }
    }
    class Program
    {
        static int[,] stoku = new int[9, 9];
        static List<xypos> emptyList = new List<xypos>();
        static xypos rtn(int i, int j)
        {
            xypos hi = new xypos(i, j);
            return hi;
        }
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            for(int i = 0; i < 9; i++)
            {
                string ipt = sr.ReadLine();
                for(int j = 0; j < 9; j++)
                {
                    stoku[i, j] = int.Parse(ipt.Split(' ')[j]);
                    if (stoku[i, j] == 0) emptyList.Add(rtn(i, j));
                }
            }
            solve(0);
        }
        static void solve(int idx)
        {
            if (idx == emptyList.Count)
            {
                StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
                //sw.Write('\n');
                for (int i = 0; i < 9; i++)
                {
                    for (int j = 0; j < 9; j++)
                    {
                        sw.Write("{0} ", stoku[i, j]);
                    }
                    sw.Write('\n');
                }
                
                sw.Flush();
                Environment.Exit(0);
            }
            for(int i = 1; i <= 9; i++)
            {
                stoku[emptyList[idx].x, emptyList[idx].y] = i;
                if (isEnble(emptyList[idx].x, emptyList[idx].y))
                {
                    //Console.WriteLine("{0} {1} {2} true", emptyList[idx].x, emptyList[idx].y, i);
                    solve(idx + 1);
                }
                else
                {
                    stoku[emptyList[idx].x, emptyList[idx].y] = 0;
                    //Console.WriteLine("{0} {1} {2} false", emptyList[idx].x, emptyList[idx].y, i);
                }
            }
        }
        static bool isEnble(int x,int y)
        {
            bool[] c = new bool[10];
            for (int i = 0; i <= 9; i++) c[i] = false;
            
            for(int i = 0; i < 9; i++)
            {
                if (stoku[x, i] == 0) continue;
                if (c[stoku[x, i]]) return false;
                c[stoku[x, i]] = true;
            }
            //Console.WriteLine("1 pass");
            for (int i = 0; i <= 9; i++) c[i] = false;
            for (int i = 0; i < 9; i++)
            {
                if (stoku[i, y] == 0) continue;
                if (c[stoku[i, y]]) return false;
                c[stoku[i, y]] = true;
            }

            //Console.WriteLine("2 pass");
            for (int i = 0; i <= 9; i++) c[i] = false;
            for (int i = 0; i < 3; i++)
            {
                for(int j = 0; j < 3; j++)
                {
                    if (stoku[i + x / 3 * 3, j + y / 3 * 3] == 0) continue;
                    if (c[stoku[i + x / 3 * 3, j + y / 3 * 3]]) return false;
                    c[stoku[i + x / 3 * 3, j + y / 3 * 3]] = true;
                }
            }

            //Console.WriteLine("3 pass");
            return true;
        }
    }
}

paraworld 3년 전 2

반례입니다.

0 6 0 0 0 0 2 0 9
0 0 0 8 2 0 5 0 0
0 1 0 9 0 3 0 0 0
3 7 0 0 9 0 0 0 6
1 0 0 0 0 0 0 0 8
2 0 0 0 4 0 0 5 1
0 0 0 5 0 4 0 9 0
0 0 3 0 7 9 0 0 0
5 0 9 0 0 0 0 6 0

위 입력에 대해 아무것도 출력하지 않네요.

dayo05 3년 전 0

이유가 멀까여...?

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례좀 찾아주세요 ㅠㅠ

dayo05 3년 전 0

paraworld 3년 전 2

dayo05 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말