网易互娱23届实习笔试

一、输入：

输入一个3x3数独，字符'.'代表空
输入三个宫的域，每个宫包括三个位置，[0,0]表示0行0列

二、输出要求：

1.每个宫里最终123各出现一次，

2.数独中的行列里不出现重复字符；

输出满足条件的解

思想：先根据输入找到所有行列不重复的数独，再判断三个宫是否满足不重复；

  1 #include <iostream>

  2 #include <bits/stdc++.h>

  3 using namespace std;

  4 int a[3][3];//存储三个宫区域

  5 int cnt;//记录满足的个数

  6 bool isValid(int row, int col, char val, vector<vector<char>>& board) {

  7     for (int i = 0; i < 3; i++) { // 判断行里是否重复

  8         if (board[row][i] == val) {

  9             return false;

 10         }

 11     }

 12     for (int j = 0; j < 3; j++) { // 判断列里是否重复

 13         if (board[j][col] == val) {

 14             return false;

 15         }

 16     }

 17     return true;

 18 }

 19 bool func(vector<vector<char>> board){

 20     for (int i = 0; i<3;i++){  //第i个宫

 21         int  vec[3];

 22         memset(vec,0,sizeof(vec));

 23         for (int j = 0; j < 3;j++){

 24             if (vec[board[a[i][j]/3][a[i][j]%3]-'1']==1){

 25                 return false;

 26                 cout <<"失败"<< a[i][j] << endl;

 27             }

 28             vec[board[a[i][j] / 3][a[i][j] % 3]-'1'] = 1;

 29         }

 30     }

 31     return true;

 32 }

 33

 34 bool backtracking(vector<vector<char>>& board) {

 35     int x, y;

 36     for (int i = 0; i < board.size(); i++) {        // 遍历行

 37         for (int j = 0; j < board[0].size(); j++) { // 遍历列

 38             x = i;

 39             y = j;

 40             if (board[i][j] != '.') continue;

 41             for (char k = '1'; k <= '3'; k++) {     // (i, j) 这个位置放k是否合适

 42                 if (isValid(i, j, k, board)) {

 43                     board[i][j] = k;                // 放置k

 44                     if (backtracking(board)) {

 45                         return true; // 如果找到合2 适一组立刻返回

 46                     }

 47                     board[i][j] = '.';              // 回溯，撤销k

 48                 }

 49             }

 50             return false;                           // 9个数都试完了，都不行，那么就返回false

 51         }

 52     }

 53     if(x==2&&y==2){ //判断是否满足宫

 54         if(func(board)){

 55             cout << "cnt++:" << endl;

 56             cnt++;

 57             for(int i=0;i<3;i++){

 58                 for(int j=0;j<3;j++){

 59                     cout<<board[i][j]<<" ";

 60                 }

 61                 cout << endl;

 62             }

 63         }

 64         /*for(int i=0;i<3;i++){

 65                 for(int j=0;j<3;j++){

 66                     cout<<board[i][j]<<" ";

 67                 }

 68                 cout << endl;

 69             }*/

 70     }

 71     return false;

 72     //return true; // 遍历完没有返回false，说明找到了合适棋盘位置了

 73 }

 74

 75 int main() {

 76     cnt = 0;

 77     vector<vector<char>>board={{0,0,0},{0,0,0},{0,0,0}};

 78     for(int i=0;i<3;i++){

 79         for(int j=0;j<3;j++){

 80             char ch;

 81             cin>>ch;

 82             board[i][j]=ch;

 83             //cout<<ch<<endl;

 84         }

 85     }

 86     int x, y;

 87         for (int i = 0; i < 3;i++){

 88             for (int j = 0; j < 3;j++){

 89                 cin >> x >> y;

 90                 a[i][j] = 3 * x + y;

 91                 //cout << 3 * x + y;

 92             }

 93         }

 94     cout << endl;

 95     cout << "x" << endl;

 96     backtracking(board);

 97     int coun = cnt;

 98     cout << "answer " << cnt << endl;

 99     return 0;

100 }

测例1：

输入

..3 ... ...

0 0 1 0 1 1

0 1 0 2 1 2

2 0 2 1 2 2

输出：

cnt++:

1 2 3

2 3 1

3 1 2

cnt++:

2 1 3

1 3 2

3 2 1

answer 2

巴特西

网易互娱23届实习笔试_3x3锯齿数独

最新文章

热门文章