B - Find snuke Editorial by en_translator
Let us call a tuple \((C_1,C_2,C_3,C_4,C_5)\) of five cells good if
they satisfy all but the first condition of contiguous cells (going vertically, horizontally, or diagonally) with s
, n
, u
, k
, and e
written on them; in other words, if:
- \(C_i\) and \(C_{i+1}\) share a side or corner for \(1\leq i\leq 4\); and
- the centers of \(C_1,C_2,C_3,C_4\), and \(C_5\) are on a common line at regular intervals.
Once \(C_1\) and \(C_2\) are fixed, the candidates of \(C_3\), \(C_4\), and \(C_5\) such that \((C_1,C_2,C_3,C_4,C_5)\) is good is uniquely determined.
Specifically, let \((i,j)\) denote the cell at the \(i\)-th row and \(j\)-th column, \(C_1=(x_1,y_1)\), and \(C_2=(x_2,y_2)\), then \((C_1,C_2,C_3,C_4,C_5)\) is good only if \(C_i=(x_1+(i-1)(x_2-x_1),y_1+(i-1)(y_2-y_1))\). Such cells may not actually exist, in which case there is no good tuple corresponding to these \(C_1\) and \(C_2\).
Now, since \(C_1\) and \(C_2\) should at least share a corner, once \(C_1\) is fixed, there are at most \(8\) possible candidates for \(C_2\). Thus, there are at most \(8HW\) good tuples in the grid, so
and a tuple of contiguous cells (going vertically, horizontally, or diagonally) with s
, n
, u
, k
, and e
written on them are constrained to them, so it is sufficient to check for all good tuple if it satisfies the first condition in the problem statement (whether \(C_1,C_2,C_3,C_4\), and \(C_5\) have s
, n
, u
, k
, and e
written on them, respectively). There are at most \(40HW(\leq 4\times10^5)\) cells to inspect, so it is sufficiently fast.
Therefore, the problem has been solved.
Sample code in C++:
#include <bits/stdc++.h>
using namespace std;
int main() {
int n,m,x,y;
int dx[8]={-1,-1,-1,0,0,1,1,1};
int dy[8]={-1,0,1,-1,1,-1,0,1};
string str;
cin>>n>>m;
vector<string> s(n);
for(int i=0;i<n;i++)cin>>s[i];
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
for(int k=0;k<8;k++){
str="";
for(int t=0;t<5;t++){
x=i+t*dx[k],y=j+t*dy[k];
if((x<0)||(x>=n)||(y<0)||(y>=m))break;
str+=s[x][y];
}
if(str=="snuke"){
for(int t=0;t<5;t++){
x=i+t*dx[k]+1,y=j+t*dy[k]+1;
cout<<x<<" "<<y<<endl;
}
return 0;
}
}
}
}
return 0;
}
posted:
last update: