变形的宽搜 育才官网 HN036 涂色游戏
描述
李老师喜欢玩一种涂色游戏：
一个由 n × n 个单元格组成的白色格子纸，按照事先给定的 m 次操作，一个接一个地把白色单元格涂黑，总共在纸上涂 m 个不同的单元格。
李老师想知道，在涂黑的过程中，要出现一个边长为3的黑色方块，需要进行多少次操作？
输入描述
第一行包含两个整数 n 和 m (1 ≤ n ≤ 1000，分别表示方格纸的大小和操作次数）
然后，m 行包含操作的描述。第i行包含两个整数xi，yi（1 ≤ xi, yi ≤ n）表示第i次操作中被涂黑的方块的行号和列号。
每行上的所有数字用单个空格分隔。保证所有操作都是不同的。
操作按照输入顺序从1开始编号。方格纸的列从左到右编号，从1开始；从上到下编号，从1开始。
输出描述
在一行上打印问题的答案 —— 方格纸上至少有一个边长为3的黑色方块时的最小操作次数。
如果不存在这样的操作，打印-1。
暴力的宽搜！
#include <bits/stdc++.h>
using namespace std;
int dir[9][2]={
{0,0},{-1,0},{1,0},{0,1},{-1,1},{1,1},{0,-1},{-1,-1},{1,-1}};//分别为以一点为中心的九个方向（包括自己）
int a[1010][1010];
int n,m,x,y;
int ck(int tx,int ty){
for(int i=0;i<9;i++){
int xx=tx+dir[i][0];
int yy=ty+dir[i][1];
if(!a[xx][yy])return 0;//煤油土谷就返回0
}
return 1;
}
int main(){
cin>>n>>m;
for(int l=1;l<=m;l++){
cin>>x>>y;
a[x][y]=1;
for(int i=0;i<9;i++){
int tx=x+dir[i][0];
int ty=y+dir[i][1];
if(ck(tx,ty)){
cout<<l;
return 0;
}
}
}
cout<<"-1";
return 0;
}