[oiclass] chess piece

problem : pieces

Title Description

FJ The chessboard of is divided into R That's ok C Column , common R×C Lattice . At the beginning , If there are chessmen in a grid , Then use ‘x’ Express , If there are no chess pieces, use ‘.’ Express . Now? FJ Yes Q Operations , The format of each operation is to give two integers ：a and b, It means to ask so far , Distance No a Xing di b Where is the nearest piece in the grid ？ Output the grid where the piece is located and the a Xing di b Column grid distance . When you output the distance ,FJ In the a Xing di b Add a chess piece to the grid of the column . Now give the formula for calculating the distance between two lattices ： Note No a Xing di b The grid in the column is （a,b), The first c Xing di d The grid in the column is （c,d), So lattice (a,b) And grid (c,d) Distance of =（a-c) × (a-c) + (b-d)×(b-d).

Input

first line ,R and C. 1 <= R, C <= 500.
Next is R That's ok C Row chessboard , Each element is either x’, Or ‘.’, The data guarantees at least one piece .
Next line , It's an integer Q, It means that there is a total of Q Operations .1<=Q<=100000.
Next there is Q That's ok , Each line represents an operation , The format is two integers ：a and b. The meaning is as shown in the title .

Output

common Q That's ok , Output one distance per line .

Examples

#1

Input

3  3
x..
...
...
3
1  3
1  1
3  2

Output

4
0
5

Tips

Sample explanation

The chessboard is 3 That's ok 3 Column , At first, there was only the 1 Xing di 1 There are chessmen in the column .
FJ All in all 3 Operations , First action ： Ask about Li di 1 Xing di 3 List the grid where the nearest chess piece is located and the 1 Xing di 3 What is the distance between the columns ？ So far, there are only 1 Xing di 1 There are chess pieces listed , Then the answer must be ：(1-1)*(1-1) + (1-3)*(1-3)=4. So you have to output 4. then FJ In the 1 Xing di 3 Add a chess piece to the grid of the column .
Second operation ： Ask about Li di 1 Xing di 1 List the grid where the nearest chess piece is located and the 1 Xing di 1 What is the distance between the columns ？ Although so far there have been two pieces , But apparently , The first 1 Xing di 1 The chess pieces in the column are closer , Then the answer must be ：(1-1)*(1-1) + (1-1)*(1-1)=0. So you have to output 0. then FJ In the 1 Xing di 1 Add a chess piece to the grid of the column .
Third operation ： Ask about Li di 3 Xing di 2 List the grid where the nearest chess piece is located and the 3 Xing di 2 What is the distance between the columns ？ Although so far there have been 3 A chess piece , The answer is ： (1-3)*(1-3) + (1-2)*(1-2)=5. So you have to output 5. then FJ In the 3 Xing di 2 Add a chess piece to the grid of the column .
about 30% The data of ,```Q <= 500``.

Previous ideas

I have thought a lot about this question , Using a number to assemble the position of the chess pieces will TLE. If you search the nearby points, you will also TLE, It is even more important if you search directly TLE.

#include<bits/stdc++.h>
using namespace std;
struct node{
    
    int x,y;
};
const int N = 250010;
int n,m;
vector<node> v;
int main(){
    
    cin >> n >> m;
    for(int i=1;i<=n;i++){
    
        for(int j=1;j<=m;j++){
    
            char c;
            cin >> c;
            if(c=='x')
                v.push_back({
    i,j});
        }
    }
    int q,a,b,ans;
    cin >> q;
    while(q--){
    
        cin >> a >> b;
        ans = 2147483647;
        for(int i=0;i<v.size();i++){
    
            ans = min(ans,(a-v[i].x)*(a-v[i].x)+(b-v[i].y)*(b-v[i].y));
        }
        v.push_back({
    a,b});
        cout <<ans <<endl;
    }
} 
/************************************************************** Language: C++ Result:  Time overrun 40 ****************************************************************/

The above code is what I use vector The highest score for variable length arrays .

AC Ideas

Later, I read the explanation of the question , It is found that this problem is also a dynamic programming problem .
set up f[i][j] For the first time i That's ok , The first j Minimum distance of columns .
Then the state transitions ：
f[i][j] = min(f[i][j],p(j-k))
there p() It means square .
It may be a little difficult to understand
Let's start with the effect ： Time complexity O((k+n)*q+k*n)
This method is to split the map into multiple horizontal one-dimensional arrays , Let him update only this line when updating , To get it, you should traverse the vertical one to see which horizontal distance + The line number of this line goes to b（ That is, the vertical distance ） The minimum output value is OK . After that, we don't need to update the whole picture , Just update all the numbers in this row .
If you still don't understand , Code up ！

#include<bits/stdc++.h>
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)
 
using namespace std;
const int INF = 1234567890;
char mp[510][510];
int f[510][510],n,m,q;
//vector<int> v[2];
int p(int x){
    return (x)*(x);}
int main(){
    
    cin >> n >> m;for(int i=1;i<=n;i++)
        scanf("%s",mp[i]+1);
    for(int i=1;i<=n;i++){
    
        for(int j=1;j<=m;j++){
    
            f[i][j] = INF;
            for(int k=1;k<=m;k++){
    
                if(mp[i][k]=='x'){
    
                    f[i][j] = min(f[i][j],p(j-k));
                } 
            }
        }
    } 
    scanf("%d",&q);
    int a,b;
    while(q--){
    
        scanf("%d%d",&a,&b);
        int ans=INF;
        for(int i=1;i<=n;i++){
    
            ans = min(f[i][b]+p(a-i),ans);
        } 
        printf("%d\n",ans);
        mp[a][b] = 'x';
        for(int j=1;j<=m;j++){
    
            f[a][j] = min(f[a][j],p(j-b));
        }
    }
    return 0;
} 
/************************************************************** Language: C++ Result:  correct 100 Time:748 ms Memory:2984 kb ****************************************************************/

This is AC Code for , Here I put cin and cout Changed to scanf and printf, Then a locomotive was added , Otherwise, there are still some problems .

Thank you for watching ！