人工智能

时间限制: 1 Sec  内存限制: 128 MB

题目描述

人胖了就容易打瞌睡，打瞌睡又会导致长胖，这对小Ｘ的减重计划很不利，于是小Ｘ决定做点动脑子的事来抵御瞌睡虫的进袭，小Ｘ决定响应国务院的号召投身到人工智能的研究开发大潮中去，具体研究什么好呢？小Ｘ再三思考后决定开发国际象棋的人工智能软件，虽然国际象棋的软件已经能够战胜人类世界冠军了，但那是基于搜索的 AI(AI 是人工智能的简称)，小Ｘ想写一个基于机器学习的国际象棋 AI，目标是战胜 IBM 的深蓝，小Ｘ的国际象棋水平也不差，曾获得过市青少年比赛的冠军，机器学习顾名思义就是让机器像人一样学习，小Ｘ首先训练机器学习棋子对棋盘的控制，具体做法是小Ｘ先在棋盘上放置若干个车和后，然后让机器判断有多少个格子没有被车和后控制到。
车和后的吃子规则如下：车：横、竖均可以走，步数不受限制，但不能斜着走。后：横、竖、斜都可以走，步数不受限制。无论是车还是后都不能越过棋子去吃子，用作训练的国际象棋棋盘可以放大缩小，并不限于 8×8 的棋盘，车和后所在的位置当然是被控制的，它们能走到的位置也都被控制。

 

输入

第一行包含一个正整数 n，表示棋盘的大小
接下来 n 行，每行 n 个整数，其中 0 表示棋盘上这个格子为空的，1 表示为车，2 表示为后

 

输出

一行一个整数，表示没有被控制到的格子数量

 

 

样例输入

复制样例数据

5
0 0 0 0 0
0 1 0 1 0
0 0 2 0 0
0 1 0 1 0
0 0 0 0 0

样例输出

4

 

提示


红色格子为样例中被控制到的格子，中间那个后能够斜着走到四个角落的格子(图中白色的格子)，但因受到四个车的阻隔而不能控制到那四个格子！
数据范围
20%的数据，保证棋盘上只有车
50%的数据，n<=50
80%的数据，n<=200
100%的数据，n<=1000，车的数量<=n*n，后的数量<=n

先将che，hou放进容器中，这样就不需要在暴力枚举一遍了。che只需要扫一遍行和列，遇到有che或者hou就终止

对于hou，需要考虑行和列，对于一个知识点需要知道

主对角线横坐标-纵坐标的的值相同，次对角线横坐标+纵坐标的值相同。

注意的地方就是遇到扫行，列，斜线时遇到che和hou要终止。

 

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

int n, a[1005][1005], vis[1005][1005], ans;

struct node
{
	int x, y;
};

vector<node> vechou, vecche;

void solvehou(int x, int y){
	int t1 = x - y, t2 = x + y;
	for (int i = x + 1; i <= n; i++){ //主对角线往下
		if(i - t1 < 1 || i - t1 > n || vis[i][i - t1] == 2) break;
		if(!vis[i][i - t1]) ans++;
		vis[i][i - t1] = 1;
	}
	for (int i = x - 1; i >= 1; i--){//主对角线往上
		if(i - t1 < 1 || i - t1 > n || vis[i][i - t1] == 2) break;
		if(!vis[i][i - t1]) ans++;
		vis[i][i - t1] = 1;
	}
	for (int i = x + 1; i <= n; i++){//次对角线往下
		if(t2 - i < 1 || t2 - i > n || vis[i][t2 - i] == 2) break;
		if(!vis[i][t2 - i]) ans++;
		vis[i][t2 - i] = 1;
	}
	for (int i = x - 1; i >= 1; i--){//次对角线往上
		if(t2 - i < 1 || t2 - i > n || vis[i][t2 - i] == 2) break;
		if(!vis[i][t2 - i]) ans++;
		vis[i][t2 - i] = 1;
	}
}

void solveche(int x, int y){
	for (int i = y + 1; i <= n; i++){
		if(vis[x][i] == 2) break;
		else if(!vis[x][i]) vis[x][i] = 1, ans++;
	}
	for (int i = y - 1; i >= 1; i--){
		if(vis[x][i] == 2) break;
		else if(!vis[x][i]) vis[x][i] = 1, ans++;
	}
	for (int i = x + 1; i <= n; i++){
		if(vis[i][y] == 2) break;
		else if(!vis[i][y]) vis[i][y] = 1, ans++;
	}
	for (int i = x - 1; i >= 1; i--){
		if(vis[i][y] == 2) break;
		else if(!vis[i][y]) vis[i][y] = 1, ans++;
	}
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	scanf("%d", &n);
	
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){
			scanf("%d", &a[i][j]);
			if(a[i][j] == 2) vechou.push_back(node{i, j}), vis[i][j] = 2;
			else if(a[i][j] == 1) vecche.push_back(node{i, j}), vis[i][j] = 2;
		}
	}
	int hou = vechou.size(), che = vecche.size();
	for (int i = 0; i < hou; i++){
		int x = vechou[i].x, y = vechou[i].y;
		solvehou(x, y);
		solveche(x, y);
		
	}
	for (int i = 0; i < che; i++){
		int x = vecche[i].x, y = vecche[i].y;
		solveche(x, y);
	}
	printf("%d\n", n *n - ans - hou - che);

	return 0;
}
/**/