[TIOJ 1238] 萬磁王的遊戲 Magneto's Game

這題在我前年暑假參加 IMOCamp 的時候就看過了，竟然在這裡出現，真是太神奇了XD

作法：

可以把鐵塊全部塞成一格 <=> 全部鐵塊連通！！！

有了這個結論，剩下就簡單了，以下給一個大概的證明。

從左邊推到右邊是顯然的。如果全部的鐵塊連通，我們只要證明能夠把其中兩個鐵塊弄到同一個格子裡，就可以數歸下去了。

考慮任兩個鐵塊 A和B ，我們想要把 A和B 弄到同一個格子裡。因為A和B連通，所以存在一條路徑連接A和B，考慮A走到B的最短路，並且沿著最短路的方向移動鐵塊們( 例如第一步A要往下走 就作往下的操作 )，如果在動的過程中，某一步B被擋住了，這就代表A和B之間的最短路距離嚴格變小了，所以可以數歸下去。而如果B一直都沒有被擋住，那這時A移動到了B的位置，因為他們走的步都一樣，所以B到的位置是B + AB向量，一直重複這個過程，如果B永遠都沒有被擋住，就會得到這個網格是無限大的，矛盾，所以A總能嚴格減少和B之間的最短距離。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=500+10 ;
 
char G[maxn][maxn] ;
int dx[]={1,-1,0,0},dy[]={0,0,1,-1} ;
int n ;
bool vis[maxn][maxn] ;
 
bool solve()
{
    int x0=-1,y0=-1 ;
    for(int i=0;i<n;i++) for(int j=0;j<n;j++)
        if(G[i][j]=='x') x0=i , y0=j ;
    if(x0==-1) return 1 ;
 
    queue<int> q ;
    q.push(x0) ; q.push(y0) ; vis[x0][y0]=1 ;
    while(!q.empty())
    {
        int x=q.front() ; q.pop() ;
        int y=q.front() ; q.pop() ;
        for(int i=0;i<4;i++)
        {
            int nx=x+dx[i] , ny=y+dy[i] ;
            if(nx<0||nx>=n||ny<0||ny>=n) continue ;
            if(G[nx][ny]=='#' || vis[nx][ny]) continue ;
            vis[nx][ny]=1 ;
            q.push(nx) ; q.push(ny) ;
        }
    }
    for(int i=0;i<n;i++) for(int j=0;j<n;j++)
        if(G[i][j]=='x' && !vis[i][j]) return 0 ;
    return 1 ;
}
 
main()
{
    scanf("%d",&n) ;
    for(int i=0;i<n;i++) scanf("%s",G[i]) ;
    if(solve()) printf("Strong!\n") ;
    else printf("Weak!\n") ;
}