Solution UVA: 10010 - Where's Waldorf?

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss10010 - Where's Waldorf?	Accepted	C++11	0.060	0.000	7265	4 mins ago

Hint by ttlcmos:

The obvious solution may become too long and have many repetitive lines.

The advice is to test (i, j) position as a key words location immediately for all the possible directions and be carefull with array borders.

#include<bits/stdc++.h>

using namespace std;

string s, st;

int r, c, x, y;    

char a[1001][1001];

int dx[]={-1,0,1,0,-1,1,1,-1};

int dy[]={0,1,0,-1,1,1,-1,-1};

void process(){

    for(int i=1; i<=r; i++)

    for(int j=1; j<=c; j++)

    for(int k=0; k<8; k++){

       

        st="";

        int u=i, v=j;

       

        for(int l=1; l<=s.size(); l++){

            st += a[u][v];

            u += dx[k];

            v += dy[k];

            if (u < 1 || v < 1 || u > r || v > c) break;

        }

       

        if (st==s)

            if (x > i) x= i, y= j;

            else

            if (x == i && y > j) x= i, y= j;    

    }

    cout<<x<<" "<<y<<"\n";          

}

int main(){

    ios::sync_with_stdio(false); cin.tie(nullptr);

   

    int t;  cin >> t;

    while(t--){

        cin >> r >> c;

        for(int i=1; i<=r; i++)

        for(int j=1; j<=c; j++)

            cin >> a[i][j], a[i][j]= toupper(a[i][j]);

       

        int q;  cin >> q;

        while(q--){

            x= r, y= c;

            cin >> s;

            for(int i=0; s[i]; i++) s[i]= toupper(s[i]);

            process();

        }

        if (t) cout<<"\n";

    }

}