- 数独验证
- 2019-08-18 19:42:16 @
下面代码为什么会在运行时超长?怎么改进?
#include <iostream>
using namespace std;
int n;
bool judgeRightHeng(int shudu[9][9],int i)
{
int temp[10] = {0,0,0,0,0,0,0,0,0,0};
for(int j = 9 * i;j < 9 * i + 9 ;j++)
{
for(int k = 0;k < 9;k++)
{
if(temp[shudu[j][k]] != shudu[j][k])
{
temp[shudu[j][k]] = shudu[j][k];
}
else
{
return true;
}
}
for(int j = 0;j < 10;j++)
{
temp[j] = 0;
}
}
return false;
}
bool judgeRightShu(int shudu[9][9],int i)
{
int temp[10] = {0,0,0,0,0,0,0,0,0,0};
for(int k = 0;k < 9;k++)
{
for(int j = 9 * i;j < 9 * i + 9 ;j++)
{
if(temp[shudu[j][k]] != shudu[j][k])
{
temp[shudu[j][k]] = shudu[j][k];
}
else
{
return true;
}
}
for(int j = 0;j < 10;j++)
{
temp[j] = 0;
}
}
return false;
}
bool judgeRightFang(int shudu[9][9],int i)
{
int temp[10] = {0,0,0,0,0,0,0,0,0,0};
for(int j = 9 * i;j < 9 * i + 9;j += 3)
{
for(int k = 0;k < 9;k += 3)
{
for(int l = j;l < j + 3;l++)
{
for(int m = k;m < k + 3;m++)
{
if(temp[shudu[l][m]] != shudu[l][m])
{
temp[shudu[j][k]] = shudu[j][k];
}
else
{
return true;
}
}
}
for(int j = 0;j < 10;j++)
{
temp[j] = 0;
}
}
}
return false;
}
string judgeRight(int shudu[9][9],int i)
{
bool a = judgeRightHeng(shudu,i);
bool b = judgeRightShu(shudu,i);
bool c = judgeRightFang(shudu,i);
if(a || b || c)
{
return "Wrong";
}
return "Right";
}
int main()
{
cin >> n;
int shudu[n][9][9];
for(int i = 0;i < n;i++)
{
for(int j = 9 * i;j < 9 * i + 9 ;j++)
{
for(int k = 0;k < 9;j++)
{
cin >> shudu[i][j][k];
}
}
}
for(int i = 0;i < n;i++)
{
cout << judgeRight(shudu[i],i);
}
/*
以下为错误代码
for(int i = 0;i < n;i++)
{
for(int j = 9 * i;j < 9 * i + 9 ;j++)
{
for(int k = 0;k < 9;k++)
{
sum += shudu[j][k];
pro *= shudu[j][k];
}
if(sum != 45)
{
flag = false;
}
if(pro != 362880)
{
flag = false;
}
sum = 0;
pro = 1;
}
for(int k = 0;k < 9;k++)
{
for(int j = 9 * i;j < 9 * i + 9 ;j++)
{
sum += shudu[j][k];
pro *= shudu[j][k];
}
if(sum != 45)
{
flag = false;
}
if(pro != 362880)
{
flag = false;
}
sum = 0;
pro = 1;
}
for(int j = 9 * i;j < 9 * i + 9;j += 3)
{
for(int k = 0;k < 9;k += 3)
{
for(int l = j;l < j + 3;l++)
{
for(int m = k;m < k + 3;m++)
{
sum += shudu[l][m];
pro *= shudu[l][m];
}
}
if(sum != 45)
{
flag = false;
}
if(pro != 362880)
{
flag = false;
}
sum = 0;
pro = 1;
}
}
if(flag)
{
cout << "Right" << endl;
}
else
{
cout << "Wrong" << endl;
}
}
*/
return 0;
}
0 条评论
目前还没有评论...