L3-037 奪寶大賽
分數 30
作者 陳越
單位 浙江大學
奪寶大賽的地圖是一個由 n×m 個方格子組成的長方形，主辦方在地圖上標明了所有障礙、以及大本營寶藏的位置。參賽的隊伍一開始被隨機投放在地圖的各個方格里，同時開始向大本營進發。所有參賽隊從一個方格移動到另一個無障礙的相鄰方格（“相鄰”是指兩個方格有一條公共邊）所花的時間都是 1 個單位時間。但當有多支隊伍同時進入大本營時，必將發生火拼，造成參與火拼的所有隊伍無法繼續比賽。大賽規定：最先到達大本營并能活著奪寶的隊伍獲得勝利。
假設所有隊伍都將以最快速度沖向大本營，請你判斷哪個隊伍將獲得最后的勝利。

輸入格式：
輸入首先在第一行給出兩個正整數 m 和 n（2<m,n≤100），隨后 m 行，每行給出 n 個數字，表示地圖上對應方格的狀態：1 表示方格可通過；0 表示該方格有障礙物，不可通行；2 表示該方格是大本營。題目保證只有 1 個大本營。
接下來是參賽隊伍信息。首先在一行中給出正整數 k（0<k<m×n/2），隨后 k 行，第 i（1≤i≤k）行給出編號為 i 的參賽隊的初始落腳點的坐標，格式為 x y。這里規定地圖左上角坐標為 1 1，右下角坐標為 n m，其中 n 為列數，m 為行數。注意參賽隊只能在地圖范圍內移動，不得走出地圖。題目保證沒有參賽隊一開始就落在有障礙的方格里。

輸出格式：
在一行中輸出獲勝的隊伍編號和其到達大本營所用的單位時間數量，數字間以 1 個空格分隔，行首尾不得有多余空格。若沒有隊伍能獲勝，則在一行中輸出 No winner.

輸入樣例 1：
5 7
1 1 1 1 1 0 1
1 1 1 1 1 0 0
1 1 0 2 1 1 1
1 1 0 0 1 1 1
1 1 1 1 1 1 1
7
1 5
7 1
1 1
5 5
3 1
3 5
1 4
輸出樣例 1：
7 6
樣例 1 說明：
七支隊伍到達大本營的時間順次為：7、不可能、5、3、3、5、6，其中隊伍 4 和 5 火拼了，隊伍 3 和 6 火拼了，隊伍 7 比隊伍 1 早到，所以獲勝。

輸入樣例 2：
5 7
1 1 1 1 1 0 1
1 1 1 1 1 0 0
1 1 0 2 1 1 1
1 1 0 0 1 1 1
1 1 1 1 1 1 1
7
7 5
1 3
7 1
1 1
5 5
3 1
3 5
輸出樣例 2：
No winner.
代碼長度限制
16 KB
Java (javac)
時間限制
800 ms
內存限制
256 MB
其他編譯器
時間限制
400 ms
內存限制
64 MB
棧限制
8192 KB
原來圖論還可以這樣打，原來我也是能做對L3的
上代碼

#include <bits/stdc++.h>
using namespace std;
const int N=2e2+9;
int g[N][N],d[N][N];
typedef long long ll;
typedef pair<int,int> pii;
vector<pii>s;
int x,y;
int xx[4]={0,0,-1,1};
int yy[4]={-1,1,0,0};
int cnt[N];
int n,m;
void dfs(){queue<pii>q;q.emplace(x,y);//q.push({x,y});while(!q.empty()){pii z=q.front();q.pop();for(int i=0;i<4;i++){int dx=z.first+xx[i];int dy=z.second+yy[i];if(dx<1||dy<1||dx>n||dy>m)continue;if(!g[dx][dy]||d[dx][dy])continue;q.emplace(dx,dy);d[dx][dy]=d[dx-xx[i]][dy-yy[i]]+1;}}
}
void solve() {cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>g[i][j];if(g[i][j]==2){x=i,y=j;}}}int k;cin>>k;for(int i=1;i<=k;i++){int a,b;cin>>a>>b;swap(a,b);s.push_back({a,b});}dfs();for(int i=0;i<k;i++){cnt[d[s[i].first][s[i].second]]++;}int mi=999,id=-1;for(int i=0;i<k;i++){int z=d[s[i].first][s[i].second];if(cnt[z]==1&&z<mi&&z)mi=z,id=i+1;}if(id==-1){cout<<"No winner.";}else cout<<id<<' '<<mi;
}
int main() {solve();return 0;
}