在code::block上写的,如果把输出注释掉过样例就会直接因为不知名错误out
#include <iostream>
#include <cstring>
#include <algorithm>
#include <bitset>
using namespace std;
const int N = 9, M = 110;
string s;
int r[N], c[N], b[N];
bool st[M];
int stk[100], top = 0, mp[N][N] = {
{0, 0, 0, 1, 1, 1, 2, 2, 2},
{0, 0, 0, 1, 1, 1, 2, 2, 2},
{0, 0, 0, 1, 1, 1, 2, 2, 2},
{3, 3, 3, 4, 4, 4, 5, 5, 5},
{3, 3, 3, 4, 4, 4, 5, 5, 5},
{3, 3, 3, 4, 4, 4, 5, 5, 5},
{6, 6, 6, 7, 7, 7, 8, 8, 8},
{6, 6, 6, 7, 7, 7, 8, 8, 8},
{6, 6, 6, 7, 7, 7, 8, 8, 8}
};
void init(){
memset(r, 0, sizeof r);
memset(c, 0, sizeof c);
memset(b, 0, sizeof b);
memset(st, false, sizeof st);
return;
}
int get(){
int minv = N, loc;
for (int i = 0, k = 0; i < N; i ++ )
for (int j = 0; j < N; j ++ , k ++ )
if (!st[k] && s[k] == '.'){
int state = r[i] | c[j] | b[mp[i][j]], t = 0;
for(int i = 1; i <= N; i ++ ) t += !(state >> i & 1);
if(t < minv) minv = t, loc = k;
}
st[loc] = true;
return loc;
}
bool dfs(int u, string &res){
if (u == -1) return true;
int ne = get(), x = ne / 9, y = ne % 9;
int state = r[x] | c[y] | b[mp[x][y]];
for (int i = 1, j = 2; i <= N; i ++ , j <<= 1)
if (!(state & j)){
r[x] |= j, c[y] |= j, b[mp[x][y]] |= j;
res[ne] = i + '0';
if(dfs(u - 1, res)) return true;
r[x] ^= j, c[y] ^= j, b[mp[x][y]] ^= j;
}
return false;
}
int main(){
while (cin >> s, s != "end"){
init();
// for(int i = 0; i < N; i ++ ) cout << (bitset<32>)r[i] << endl;
// puts("");
// for(int j = 0; j < N; j ++ ) cout << (bitset<32>)c[j] << endl;
// puts("");
// for(int k = 0; k < N; k ++ ) cout << (bitset<32>)b[k] << endl;
// puts("");
int cnt = 0;
string res(81, ' ');
for (int i = 0, k = 0; i < N; i ++ )
for (int j = 0; j < N; j ++ , k ++ )
if (s[k] != '.'){
int t = 1 << (s[k] - '0');
r[i] |= t, c[j] |= t, b[mp[i][j]] |= t;
res[k] = s[k];
}
else cnt ++ ;
dfs(cnt, res);
cout << res << endl;
}
return 0;
}
如果加上输出的话那么样例的第一条能过,第二条不能过。 重启之后发现不加输出第一次能过第一条,之后第一条还是会out。
会不会是内存分配的问题呢QωQ
有没有大佬解答一下。