蒟蒻求调
  • 板块P1784 数独
  • 楼主tysgk
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/1/18 15:32
  • 上次更新2023/10/24 03:43:30
查看原帖
蒟蒻求调
798860
tysgk楼主2023/1/18 15:32
#include <bits/stdc++.h>
using namespace std ;
int flag ; 
int Map[ 11 ][ 11 ] ; //地图 
int Map1[ 11 ][ 11 ] ;
bool vis[ 11 ][ 11 ] ; //用于判断当前位置是否能填数 
bool mx[ 10 ][ 10 ] , my[ 10 ][ 10 ] ; //每一行列可填的数 
void dfs ( int x , int y ) {
	if ( flag == 1 ) {
		return ;
	}
	if ( Map[ x ][ y ] != 0 ) {
		if ( x == 9 && y == 9 ) {
			flag = 1 ;
			for ( int i = 1 ; i <= 9 ; i++ ) {
				for ( int k = 1 ; k <= 9 ; k++ ) {
					Map1[ x ][ y ] = Map[ x ][ y ] ;
				}
			}
		}
		else if ( y == 9 ) dfs ( x + 1 , y ) ;
		else dfs ( x , y + 1 ) ;
	}
	else {
		for ( int i = 1 ; i <= 9 ; i++ ) {
			if ( mx[ x ][ i ] == true && my[ y ][ i ] == true && vis[ x ][ y ] == true ) {
				Map[ x ][ y ] = i ;
				mx[ x ][ i ] = my[ y ][ i ] = vis[ x ][ y ] = false ;
				if ( x == 9 && y == 9 ) {
					flag = 1 ;
				}
				else if ( y == 9 ) dfs ( x + 1 , y ) ;
				else dfs ( x , y + 1 ) ;
				Map[ x ][ y ] = 0 ;
				vis[ x ][ y ] = true ;
				mx[ x ][ i ] = my[ y ][ i ] = true ;
			}
		}
	}
	
}
int main() {
	memset ( Map , -1 , sizeof ( Map ) ) ; //将地图全部初始化为-1,以便深搜判断边界 
	for ( int i = 1 ; i <= 9 ; i++ ) {
		for ( int k = 1 ; k <= 9 ; k++ ){
			cin >> Map[ i ][ k ] ; //输入地图 
			if ( Map[ i ][ k ] != 0 ) {
				vis[ i ][ k ] = false ; //在输入的同时来判断此位置是否有数并将有数的位置标记 
				mx[ i ][ Map[ i ][ k ] ] = false ; //将用过的数用bool存为false 
			}
			else vis[ i ][ k ] = true ;
		}
	}
	vis[ 1 ][ 1 ] = 1 ;
	dfs ( 1 , 1 ) ;//从起点开始深搜 
	for ( int i = 1 ; i <= 9 ; i++ ) {
		for ( int k = 1 ; k <= 9 ; k++ ) {
			cout << Map1[ i ][ k ] << " " ;
		}
		cout << endl ;
	}
	return 0 ;
}

2023/1/18 15:32
加载中...