#include <bits/stdc++.h>

using namespace std;

void input(int arr[9][9]);//定义一个存储数独数据的函数
bool isvalid(int arr[9][9]);//判断数据是否能够构成数独，详见下面具体函数
bool isvalid(int i,int j,int arr[9][9]);//判断数独是否满足定义，详见下面具体函数

int main()
{
    cout << "Please enter a Sudoku puzzle solution" << endl;
    int arr[9][9];
    input(arr);
    if(isvalid(arr))
    {
        cout << "The Sudoku is right" << endl;
    }
    else
    {
        cout << "The Sudoku is wrong" << endl;
    }
    return 0;
}

void input(int arr[9][9])
{
    for(int i = 0; i < 9; i++)
    {
        for(int j = 0; j < 9; j++)
        {
            cin >> arr[i][j];
        }
    }
}

bool isvalid(int arr[9][9])
{
    for(int i = 0; i < 9; i++)
    {
        for(int j = 0; j < 9; j++)
        {
            if(arr[i][j] < 1 || arr[i][j] > 9 || !isvalid(i,j,arr))//第一、二个条件判断每一个数是否在1~9之间，第三个条件判断数是否满足数独的定义
            {
                return false;//如果不能构成数独的条件成立，那么就返回false
            }

        }
    }
    return true;//否则就返回return
}


bool isvalid(int i,int j,int arr[9][9])
{
    //判断每一列是否满足唯一的1~9个数
    for(int column = 0; column < 9; column++)
    {
        if(column != j && arr[i][column] == arr[i][j])//此处有些抽象，不要灰心，不要急躁，慢慢听我道来
        {
            //其实这是一个比较的过程，j和column都表示第几列，i则表示行。而此条件是在判断如果column不等于j的情况下，这是什么意思呢？
            //如果column等于j表示这两个数都在第i行第j列，则数必定相同，而我要做的是判断每一列的数都是唯一存在的，所以摒弃掉相同的列数，让不同列进行比较
            //如果有两个不同的列数相同，则不满足数独的定义（满足不同行，不同列，不同宫内的数字均含1~9，不重复），则返回false
            return false;
        }
    }
    //判断每一行是否满足唯一的1~9个数
    for(int row = 0; row < 9; row++)
    {
        if(row != i && arr[row][j] == arr[i][j])//同上可得，保证每一行数都满足1~9唯一存在的
        {
            return false;
        }
    }
    //判断每个宫内都满足1~9唯一存在的
    for(int row = (i / 3) * 3; row < (i / 3) * 3 + 3; row++)
    {
        //此步将行数分为了i / 3块，有意思的是括号内的i / 3很巧妙的把第一、二、三行列的数据都放到了第一块（因为0 / 3 = 0;1 / 3 = 0;2 / 3 =0),并分成了三大行块
        for(int column = (j / 3) * 3; column < (j / 3) * 3; column++)
        {
            //同上步道理相同
            if(column != j && row != i && arr[column][row] == arr[i][j])
            {
                //为了保证每一块的数据都满足1~9唯一存在的，如果不成立进入if，返回false
                return false;
            }
        }
    }
    return true;
}
//第一组测试数据
//9 6 3 1 7 4 2 5 8
//1 7 8 3 2 5 6 4 9
//2 5 4 6 8 9 7 3 1
//8 2 1 4 3 7 5 9 6
//4 9 6 8 5 2 3 1 7
//7 3 5 9 6 1 8 2 4
//5 8 9 7 1 3 4 6 2
//3 1 7 2 4 6 9 8 5
//6 4 2 5 9 8 1 7 3


//第二组测试数据
//2 9 7 5 1 3 4 6 8
//3 8 1 4 2 6 9 5 7
//6 5 4 9 8 7 1 2 3
//9 6 8 2 5 1 7 3 4
//1 4 3 6 7 8 5 9 2
//5 7 2 3 9 4 8 1 6
//8 3 6 1 4 5 2 7 9
//7 2 5 8 3 9 6 4 1
//4 1 9 7 6 2 3 8 5

判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。


上图是一个部分填充的有效的数独。

数独部分空格内已填入了数字，空白格用 '.' 表示。

示例 1:

输入:
[
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
输出: true
 
func isValidSudoku(board [][]byte) bool {
    var row [9][10]bool
    var cow [9][10]bool
    var block [9][10]bool
    for i := 0; i < 9; i++ {
        for j := 0; j < 9; j++ {
	var index = i/3*3 + j/3
	if board[i][j] != '.' {
	    var tmp = board[i][j] - '0'
	    if row[i][tmp] {
	        return false
	    } else {
	        row[i][tmp] = true
	    }
	    if cow[j][tmp] {
	        return false
	    } else {
	        cow[j][tmp] = true
	    }
	    if block[index][tmp] {
	        return false
	    } else {
	        block[index][tmp] = true
	    }

	}
        }

    }
    return true
}
 
 

推格子小游戏
 
 
当学习到二维数组后，我们可以运用二维数组知识实现推格子的小游戏，让我们一起来学习一下吧~
 推箱子设计流程：
 1、确定数字和字符的对应关系
 0 printf（“ ”）； 路
 1 printf（“@ ”）； 人
 2 printf（“ #”）； 墙
 3 printf(“ $“)；箱子4printf（”0“）；目标点5printf（”@“）;7printf（”$“）;
 2定义地图
 定义一个8*8的二维数组，arr[8][8]
 
3、定义记录小人位置的变量
 
4、进入死循环
 （1）、清理屏幕
 （2）、显示地图，把数字转换为对应的符号显示
 （3）、获取方向键，并处理
 1.前面是墙壁
 2.前面是路或者目标
 目标位置 +=1
 原位置 -=1
 3.前面是在路上的箱子，或者在目标上的点的箱子
 1、箱子前面是墙壁
 2、箱子前面必须是路或者目标点
 人前面的前面 +=3
 人前面 -=2
 原来的位置 -=1
 
（4）、如果箱子都到目标点后，游戏结束
 程序如下：
 
#include <stdio.h>
#include <getch.h>
#include <stdlib.h>

int main(int argc,const char* argv[])
{
	char map[8][8]={
		{0,0,2,2,2,2,0,0},
		{0,0,2,4,4,2,0,0},
		{0,2,2,0,4,2,2,0},
		{0,2,0,0,3,4,2,0},
		{2,2,0,3,0,0,2,2},
		{2,0,0,2,3,3,0,2},
		{2,0,0,1,0,0,0,2},
		{2,2,2,2,2,2,2,2}
		};

		//定义小人的位置
		char m_x = 6,m_y = 3;
		//进入死循环
		for(;;)
		{
			//清理屏幕
			system("clear");
			for(int i=0;i<8;i++)
			{
				for(int j=0;j<8;j++)
					{
						switch(map[i][j])
						{
						case 0: printf("  ");break;
						case 1: printf("@ ");break;
						case 2: printf("# ");break;
						case 3: printf("$ ");break;
						case 4: printf("0 ");break;
						case 5: printf("@ ");break;
						case 7: printf("$ ");break;
						}
					}
				printf("\n");
			}
			switch(getch())
			{
				case 183:
				if(map[m_x-1][m_y]==0 ||map[m_x-1][m_y]==4)
				{
					map[m_x-1][m_y] +=1;
					map[m_x--][m_y] -=1;
				}
				else if(map[m_x-1][m_y]==3 || map[m_x-1][m_y]==7)
				{
					if(map[m_x-2][m_y]==0 || map[m_x-2][m_y]==4)
					{
						map[m_x-2][m_y] += 3;
						map[m_x-1][m_y] -=2;
						map[m_x--][m_y] -=1;
					}
				}
				break;
				case 184:
				if(map[m_x+1][m_y]==0 ||map[m_x+1][m_y]==4)
				{
					map[m_x+1][m_y] +=1;
					map[m_x++][m_y] -=1;
				}
				else if(map[m_x+1][m_y]==3 || map[m_x+1][m_y]==7)
				{
					if(map[m_x+2][m_y]==0 || map[m_x+2][m_y]==4)
					{
						map[m_x+2][m_y] += 3;
						map[m_x+1][m_y] -=2;
						map[m_x++][m_y] -=1;
					}
				}
				break;
				case 185:
				if(map[m_x][m_y+1]==0 ||map[m_x][m_y+1]==4)
				{
					map[m_x][m_y+1] +=1;
					map[m_x][m_y++] -=1;
				}
				else if(map[m_x][m_y+1]==3 || map[m_x][m_y+1]==7)
				{
					if(map[m_x][m_y+2]==0 || map[m_x][m_y+2]==4)
					{
						map[m_x][m_y+2] += 3;
						map[m_x][m_y+1] -=2;
						map[m_x][m_y++] -=1;
					}
				}
				break;
				case 186:
				if(map[m_x][m_y-1]==0 ||map[m_x][m_y-1]==4)
				{
					map[m_x][m_y-1] +=1;
					map[m_x][m_y--] -=1;
				}
				else if(map[m_x][m_y-1]==3 || map[m_x][m_y-1]==7)
				{
					if(map[m_x][m_y-2]==0 || map[m_x][m_y-2]==4)
					{
						map[m_x][m_y-2] += 3;
						map[m_x][m_y-1] -=2;
						map[m_x][m_y--] -=1;
					}
				}
				break;
			}
	}
}

C++ STL库中的vector类似于封装了一个动态的数组，非常的好用，关于vector的一些函数，见这篇博客：
 https://blog.csdn.net/wuzhongqiang/article/details/102956793
 而这里，结合刷题过程中的学习，对知识进行一些补充和梳理。
 首先是一维数组的创建，一维数组可以直接创建，也可以通过数组的方式创建
 
int arr[] = {1, 2, 3, 4, 5}
int len = sizeof(arr) / sizeof(arr[0]);
vector<int> v(arr, arr+len)  // 利用vector的构造函数，由普通数组直接创建向量
 
下面主要记录二维数组
 今天刷了LeetCode上的一个有效数独的题目，发现用vector实现二维数组的方式比较好用，所以在这里整理一下，vector如何创建二维数组和创建完了怎么使用。
 
1. vector创建二维数组和添加元素的方式1
 
创建二维数组
 
vector<vector<char> > v;    // 这是一种方式，注意<char>后面有个空格
 
添加元素
 上面的这种方式，如果需要进行使用的话，一般得用push_back往里面加入元素。 但是注意v.push_back() 这里面必须是个向量，别的不行。
 可以下面这样添加元素：
 
//正确的插入方式
vector<vector<int> > A;
//A.push_back里必须是vector
vector<int> B;
B.push_back(0);
B.push_back(1);
B.push_back(2);
A.push_back(B);
B.clear();
B.push_back(3);
B.push_back(4);
B.push_back(5);
A.push_back(B);
 
或者用循环
 
vector<vector<int> > test;
vector<int> v;
int n,temp;
 
cin >> n;
test.clear();
 
 //输入
for (int i = 0; i<n; i++) {
   v.clear(); //每次记得clear:)
   for (int j = 0; j < n; j++)
    {
        cin >> temp;
        v.push_back(temp);
     }
        test.push_back(v);
    }

 
2. vector创建二维数组和添加元素的方式2
 
创建数组
 第二种创建数组的方式就是创建的时候直接定义好二维数组的结构（多少行，多少列）
 
//创建一个5行3列的数组
//由vector实现的二维数组，可以通过resize()的形式改变行、列值
int i,j;
vector<vector<int>> array(5);
for (i = 0; i < array.size(); i++)
    array[i].resize(3);

// 赋值
for(i = 0; i < array.size(); i++)
{
    for (j = 0; j < array[0].size();j++)
    {
        array[i][j] = (i+1)*(j+1);
    }
}
 
或者
 
vector<vector<char> > v(5, vector<char>(3)) // 创建了一个5行3列的数组
vector<vector<char> > v(5, vector<char>(3, 1)) // 创建一个5行3列的数组，并且初始化元素全为1
 
3. 二维数组的遍历
 
创建完了之后，如何像普通的二维数组那样遍历呢？
 
第一种遍历方式，类似普通的二维数组，获取行数和列数，然后遍历
 
void reverse_with_index(vector<vector<int>> vec)
{
    if (vec.empty())
    {
        cout << "The vector is empty!" << endl;
        return;
    }

    int i,j;
    cout << "Use index : " << endl;
    for (i = 0; i < vec.size(); i++)
    {
        for(j = 0; j < vec[0].size(); j++)
            cout << vec[i][j] << " ";
        cout << endl;
    }
}
 
其中， vec.size() 这是行数， vec[0].size() 这是列数
 
第二种方式，迭代器
 
void reverse_with_iterator(vector<vector<int>> vec)
{
    if (vec.empty())
    {
        cout << "The vector is empty!" << endl;
        return;
    }

    vector<int>::iterator it;
    vector<vector<int>>::iterator iter;
    vector<int> vec_tmp;

    cout << "Use iterator : " << endl;
    for(iter = vec.begin(); iter != vec.end(); iter++)
    {
        vec_tmp = *iter;
        for(it = vec_tmp.begin(); it != vec_tmp.end(); it++)
            cout << *it << " ";
        cout << endl;
    }
}
 
小总
 
其实，理解了vector的一维应用，再理解vector的二维应用应该是比较简单了，无非就是把一维数组里面的int, char等换成了又一个向量， 一些方法还是通用的。
 PS： vector里面常用的一些方法：
 
 
 
vector是一个模板类 所以使用时要用vector a 或者 vector b这样的方式来声明一个vector
 vector是一个类似于int a[]的整数数组，而vector是一个类似于string a[]的字符串数组
 clear()清空
 resize()改变大小
 push_back()在尾部添加元素
 pop_back()在尾部删除元素
 empty()测试是否为空
 vector之间可以直接赋值或者作为函数的返回值
 push_back()和pop_back()无需改变数组长度，自动会增加和减小数组长度
 增加长度后增加的元素值为0
 
 
测试代码：
 
#include <iostream>
#include <vector>
using namespace std; 
int main() 
	vector<int> a; 
	int t; 
	for (int i = 0; i < 10; i++) 
	{ 
		cin >> t; a.push_back(t); 
	} 
	vector<int> b; 
	b = a; 
	cout << "print b: 直接赋值" << endl; 
	for (int i = 0; i < b.size(); i++) 
	{ 
		cout << b[i] << " "; 
	} 
	cout << endl; 
	cout << "a.size() = " << a.size() << endl;  
	cout << "print1:" << endl; 
	for (int i = 0; i < a.size(); i++) 
	{ 
		cout << a[i] << " "; 
	} 
	cout << endl;  
	a.resize(11); 
	cout << "a.size() = after resize(11) :" << a.size() << endl; 		 
	cout << "print2 after resize(11):" << endl; 
	for (int i = 0; i < a.size(); i++) 
	{ 
		cout << a[i] << " "; 
	} 
	cout << endl;  
	a.push_back(22); 
	cout << "print3 after push_back(22):" << endl; 
	for (int i = 0; i < a.size(); i++) 
	{ 
	    cout << a[i] << " "; 
	 } 
	 cout << endl;  
	 a.pop_back(); 
	 cout << "a.size() = after pop_back() :" << a.size() << endl; 
	 cout << "print4 after pop_back():" << endl; 
	 for (int i = 0; i < a.size(); i++) 
	 { 
	 	cout << a[i] << " "; 
	 } 
	 cout << endl; 
	 cout << "a.empty()?:" << a.empty() << endl; 
	 a.clear(); 
	 cout << "a.size() = after a.clear() :" << a.size() << endl; 
	 cout << "print5 after a.clear():" << endl; 
	 for (int i = 0; i < a.size(); i++) 
	 { 
	 	cout << a[i] << " "; 
	 } 
	 cout << endl; 
return 0;
}
 
STL中vector的方法：
 
 
 
c.assign(beg,end) 将(beg; end)区间中的数据赋值给c。
 c.assign(n,elem)　将n个elem的拷贝赋值给c。
 c. at(idx)　 传回索引idx所指的数据，如果idx越界，抛出out_of_range。
 c.back()　 传回最后一个数据，不检查这个数据是否存在。
 c.begin()　 传回迭代器中的第一个数据地址。
 c.capacity()　 返回容器中数据个数。
 c.clear()　 移除容器中所有数据。
 c.empty()　 判断容器是否为空。
 c.end() // 指向迭代器中末端元素的下一个，指向一个不存在元素。
 c.erase(pos) // 删除pos位置的数据，传回下一个数据的位置。
 c.erase(beg,end)　删除[beg,end)区间的数据，传回下一个数据的位置。
 c.front()　 　 传回第一个数据。
 get_allocator　 使用构造函数返回一个拷贝。
 c.insert(pos,elem) // 在pos位置插入一个elem拷贝，传回新数据位置
 c.insert(pos,n,elem) // 在pos位置插入n个elem数据,无返回值
 c.insert(pos,beg,end) // 在pos位置插入在[beg,end)区间的数据。无返回值
 c.max_size()　 返回容器中最大数据的数量。
 c.pop_back()　 删除最后一个数据。
 c.push_back(elem)　 在尾部加入一个数据。
 c.rbegin()　 传回一个逆向队列的第一个数据。
 c.rend()　 传回一个逆向队列的最后一个数据的下一个位置。
 c.resize(num)　 　重新指定队列的长度。
 c.reserve()　 保留适当的容量。
 c.size()　 返回容器中实际数据的个数。
 c1.swap(c2) // 将c1和c2元素互换