Official

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: