d250 - 94北縣賽-2-數獨問題 (Sudoku)

🔗 前往 ZeroJudge 原題

題目描述

題目要求針對簡化的數獨題目，計算每一行中缺失的唯一數字。簡化規則為，每一行和每一列都只缺失一個數字。輸入是一個 9x9 的數獨盤面，其中包含數字 1 到 9 和 0 (代表空格)。程式需要輸出每一行中空格應該填入的數字。

解題思路

題目描述中提到每一行和每一列都只缺失一個數字，因此解題思路非常簡單。對於每一行，計算所有數字的和，然後用 45 (1+2+...+9) 減去該行的和，即可得到缺失的數字。程式直接遍歷每一行，計算每一行的數字和，並輸出缺失的數字。

複雜度分析

• 時間複雜度: O(n^2)，其中 n 是數獨盤面的大小 (在本例中為 9)。程式需要遍歷整個 9x9 的盤面。
• 空間複雜度: O(1)，程式只使用了常數級別的額外空間。

程式碼

#include <iostream>
using namespace std;
int main(){
	int b=0;
	char a[9][9]={};
	for(int i=0;i<9;i++){
		for(int j=0;j<9;j++){
			cin >> a[i][j];
		}
	}
	for(int i=0;i<9;i++){
		for(int j=0;j<9;j++){
			b+=a[i][j]-48;
		}
		cout << 45-b << endl;
		b=0;
	}
}