首页 > ACM题库 > HDU-杭电 > HDU 3476-Sudoku[解题报告]HOJ
2014
04-04

HDU 3476-Sudoku[解题报告]HOJ

Sudoku

问题描述 :

The puzzle game of Sudoku is played on a board of N^2 × N^2 cells. The cells are grouped in N × N squares of N × N cells each. Each cell is either empty or contains a number between 1 and N^2.

The Sudoku position is correct when numbers in each row, each column and each square are different. The goal of the game is, starting from some correct positions; fill all empty cells so that the final position is still correct. (We call the final position is a solution to the starting position).

This problem is not about to solve a specific Sudoku puzzle, but ask you to find all correct positions that have a unique solution when N = 2.

输入:

There’s no input for this problem.

输出:

There’s no input for this problem.

样例输出:

Hint
The Sudoku description is quoted from problem "Sudoku Checker", Northeastern Europe 2005

点击打开链接


// File Name: hdu3746.cpp
// Author: bo_jwolf
// Created Time: 2013年05月04日 星期六 19:54:29

#include<vector>
#include<list>
#include<map>
#include<set>
#include<deque>
#include<stack>
#include<bitset>
#include<algorithm>
#include<functional>
#include<numeric>
#include<utility>
#include<sstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<ctime>

using namespace std;
const int maxn = 100010 ;
char str[ maxn ] ;
int next[ maxn ] ;
void getnext( char *p )
{
	int j  , k ;
	j = 0 , k = -1 ;
	int len = strlen( p ) ;
	next[ 0 ] = -1 ;
	while( j < len )
	{
		if( k == -1 || p[ j ] == p[ k ] )
		{
			j++ ;
			k++ ;
			next[ j ] = k ;
		}
		else
			k = next[ k ] ;
	}
}


int main()
{
	int Case ;
	scanf( "%d" , &Case ) ;
	while( Case-- )
	{
		scanf( "%s" , str ) ;
		getnext( str );
		int len = strlen( str ) ;

		if( next[ len ] == 0 )
		{
			printf( "%d\n" , len ) ;
			continue ;
		}
		int t = len - next[ len ] ;
		if( len % t == 0 )
			printf( "0\n" );
		else
			printf( "%d\n" , t - len % t ) ;
	}
	return 0;
}

参考:http://blog.csdn.net/bo_jwolf/article/details/8884781


  1. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.

  2. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    O(n) = O(n-1) + O(n-2) + ….
    O(n-1) = O(n-2) + O(n-3)+ …
    O(n) – O(n-1) = O(n-1)
    O(n) = 2O(n-1)

  3. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。