#include<iostream>\n#include<vector>\n#include<time.h>\nusing namespace std;\n\nint question[10][10]{};\t\t//题目给出信息\nint rowmark[10][10]{};\t\t//行数据标签 标志第n行 数字m是否存在\nint colmark[10][10]{};\t\t//列数据标签\nint blockmark[10][10]{};\t\t//块数据标签\nint row[10]{},col[10]{},block[10]{};\nclock_t start,finish;\nclass point\n{\npublic:\n\tint r,c,n=0;\n\tpoint(int _r, int _c)\n\t{\n\t\tr=_r;\n\t\tc=_c;\n\t}\n};\nvectortofill;\nbool judge(int r,int c,int n);\nbool backtrack(int);\nvoid setmark(int r, int c, int n, bool flag);\ninline int getblocknum(int r,int c);\nvoid printboard();\nvoid Clear();\nint main(int argc, const char * argv[]) {\n\tstart=clock();\n\tint count;\n\tcin>>count;\n\twhile(count--)\n\t{\n\t\tfor(int r=1;r<10;r++)//from 1 to 9\n\t\t{\n\t\t\tfor(int c=1;c<10;c++)//from 1 to 9\n\t\t\t{\n\t\t\t\tchar ch;\n\t\t\t\tcin>>ch;\n\t\t\t\tquestion[r][c]=ch-'0';\n\t\t\t\tif(question[r][c]==0)\n\t\t\t\t{\n\t\t\t\t\ttofill.push_back(point(r,c));\n\t\t\t\t}\n\t\t\t\telse\n\t\t\t\t{\n\t\t\t\t\tsetmark(r, c, question[r][c], 1);\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t\tif(backtrack(0))\n\t\t{\n\t\t\tcout<<"\nResult:" <<endl; \n\t\t\tprintboard();\n\t\t}\n\t\tClear();\n\t}\n\tfinish=clock();\n\t//cout<<(finish-start)<<endl;\n\treturn 0;\n\t\n}\n// 修改标签，确定是否填入数据\nvoid setmark(int r, int c, int n, bool flag)\n{\n\trowmark[r][n]=flag;\n\tcolmark[c][n]=flag;\n\tblockmark[getblocknum(r, c)][n]=flag;\n}\n\ninline int getblocknum(int r,int c)\n{\n\treturn ((r-1)/3)*3+((c-1)/3);\n}\n\nbool judge(int r,int c,int n)\n{\n\treturn !rowmark[r][n]&&!colmark[c][n]&&!blockmark[getblocknum(r, c)][n];\n}\n\nvoid printboard()\n{\n\tfor(int r=1;r<10;r++)//from 1 to 9\n\t{\n\t\tfor(int c=1;c<10;c++)//from 1 to 9\n\t\t{\n\t\t\tcout<<question[r][c];\n\t\t}\n\t\tcout<<endl;\n\t}\n}\nvoid Clear()\n{\n\tfor(int i=0;i<=10;i++)\n\t{\n\t\tfor(int j=0;j<=10;j++)\n\t\t{\n\t\t\trowmark[i][j]=0;\n\t\t\tcolmark[i][j]=0;\n\t\t\tblockmark[i][j]=0;\n\t\t\tquestion[i][j]=0;\n\t\t}\n\t}\n}\n\nbool backtrack(int step)\n{\n\tif(step==tofill.size())\n\t{\n\t\treturn true;\n\t}\n\tint reverse=(int)tofill.size()-step-1;\n\tint r=tofill[reverse].r,c=tofill[reverse].c;\n\t//int r=tofill[step].r,c=tofill[step].c;\n\tfor(int i=1;i<10;i++)\n\t{\n\t\tif(judge(r, c, i))\n\t\t{\n\t\t\tquestion[r][c]=i;\n\t\t\tsetmark(r, c, question[r][c], 1);\n\t\t\tif(backtrack(step+1))return true;\n\t\t\tsetmark(r, c, question[r][c], 0);\n\t\t\tquestion[r][c]=0;\n\t\t}\n\t}\n\treturn false;\n}\n分析这段代码的时间复杂度和空间复杂度内容：时间复杂度：\n- 对于每个空白格子，都需要尝试填入1到9的数字，所以backtrack函数的时间复杂度为O(9^n)，其中n是空白格子的数量。\n- setmark函数的时间复杂度为O(1)，因为只需要修改标签数组。\n- printboard函数的时间复杂度为O(81)，因为需要遍历整个数独棋盘。\n- Clear函数的时间复杂度为O(100)，因为需要遍历整个标签数组和数独棋盘。\n- main函数的时间复杂度为O(count * 81 * 9^n)，其中count是测试用例的数量。\n\n空间复杂度：\n- 数独棋盘和标签数组都需要O(81)的空间。\n- tofill数组最多存储81个空白格子的位置，所以需要O(81)的空间。\n- 其他变量需要常数级的空间。\n- 总的空间复杂度为O(81 + 81 + 81 + 81 + 1) = O(324)。
