NC16520. 迷宫
描述
输入描述
第一行三个正整数n, m, k (2 ≤ n, m ≤ 2,000, k ≤ 100,000)。
接下来n行，每行m-1个 0/1。其中i行第j个数描述单元(i, j)和(i, j+1)之间是否存在墙。(1表示有墙，0表示没墙)
接下来n-1行，每行m个 0/1。其中i行第j个数描述单元(i, j)和(i+1, j)之间是否存在墙。(1表示有墙，0表示没墙)
接下来k行，每行两个正整数x, y，描述G中一个顶点所对应的单元，其中x代表行号，y代表列号。保证这k个顶点所对应的单元两两不同。
输出描述
输出一行一个整数，描述最小生成树的边权和。
示例1
输入:
5 5 3 0111 0010 0101 0110 0111 10000 10000 10001 10000 1 4 4 3 4 2
输出:
9
Java(javac 1.8) 解法, 执行用时: 3962ms, 内存消耗: 239876K, 提交时间: 2018-06-28 02:44:34
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.PriorityQueue;
public class Main {
InputStream is;
PrintWriter out;
String INPUT = "5 5 3\n" +
"0111\n" +
"0010\n" +
"0101\n" +
"0110\n" +
"0111\n" +
"10000\n" +
"10000\n" +
"10001\n" +
"10000\n" +
"1 4\n" +
"4 3\n" +
"4 2";
String mz[] = new String[2005], stop[] = new String[2005];
boolean tag[][] = new boolean[2005][2005];
class Node implements Comparable<Node>{
Node(long dis, int x, int y) {
this.dis = dis;
this.x = x;
this.y = y;
}
Long dis;
int x, y;
public int compareTo(Node r) {
return -dis.compareTo(r.dis);
}
}
private void solve() {
for (int i = 0; i < 2002; ++i)
Arrays.fill(tag[i], false);
long ret = 0;
int n = ni(), m = ni(), k = ni();
for (int i = 0; i < n; ++i)
mz[i] = ns();
for (int i = 0; i < n - 1; ++i)
stop[i] = ns();
int bx = 0, by = 0;
for (int i = 0; i < k; ++i) {
int x = ni(), y = ni();
x--;
y--;
tag[x][y] = true;
bx = x;
by = y;
}
long dis[][] = new long[n][m];
for (int i = 0; i < n; ++i)
Arrays.fill(dis[i], -1);
PriorityQueue<Node> q = new PriorityQueue<>();
q.add(new Node(0, bx, by));
while (!q.isEmpty()) {
Node t = q.poll();
int x = t.x, y = t.y;
long d = -t.dis;
if (dis[x][y] >= 0 && dis[x][y] <= d)
continue;
if (dis[x][y] >= 0 && tag[x][y])
continue;
if (tag[x][y]) {
ret += d;
d = 0;
}
dis[x][y] = d;
if (x + 1 < n && stop[x].charAt(y) == '0')
q.add(new Node(-d - 1,x + 1,y));
if (x > 0 && stop[x - 1].charAt(y) == '0')
q.add(new Node(-d - 1, x - 1, y));
if (y + 1 < m && mz[x].charAt(y) == '0')
q.add(new Node(-d - 1, x, y + 1));
if (y > 0 && mz[x].charAt(y - 1) == '0')
q.add(new Node(-d - 1, x, y - 1));
}
out.println(ret);
}
void run() throws Exception
{
is = oj ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
tr(System.currentTimeMillis()-s+"ms");
}
public static void main(String[] args) throws Exception { new Main().run(); }
private byte[] inbuf = new byte[1024];
public int lenbuf = 0, ptrbuf = 0;
private int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private double nd() { return Double.parseDouble(ns()); }
private char nc() { return (char)skip(); }
private String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private boolean oj = true;
//private boolean oj = System.getProperty("ONLINE_JUDGE") != null;
private void tr(Object... o) { if(!oj)System.out.println(Arrays.deepToString(o)); }
}
C++14(g++5.4) 解法, 执行用时: 1520ms, 内存消耗: 38736K, 提交时间: 2018-06-23 17:27:12
#include <bits/stdc++.h>
using namespace std;
#define www 12
struct node
{
int w, x, y;
node(int a, int b, int c): w(a), x(b), y(c){}
bool operator > (const node &a) const{
return w > a.w;
}
};
const int N = 2345;
const int M = 100110;
char s1[N][N], s2[N][N];
int v[M][2], w[N][N], n, m, k;
bool vis[N][N], h[N][N];
priority_queue<node, vector<node>, greater<node> > q;
void BFS(int x){
cout << "DBG" << x << endl;
}
int main(){
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; ++i)
scanf("%s", s1[i] + 1);
for (int i = 1; i < n; ++i)
scanf("%s", s2[i] + 1);
for (int i = 0; i < k; ++i){
scanf("%d%d", &v[i][0], &v[i][1]);
vis[v[i][0]][v[i][1]] = 1;
}
long long res = 0ll;
q.push(node(0, v[0][0], v[0][1]));
for (int i = 0; i <= n; ++i)
for (int j = 0; j <= m; ++j)
w[i][j] = -1;
while (!q.empty()){
node tmp = q.top();
q.pop();
int ww = tmp.w;
if (w[tmp.x][tmp.y] >= 0 && ((w[tmp.x][tmp.y] <= ww) || vis[tmp.x][tmp.y]))
continue;
if (vis[tmp.x][tmp.y]){
res += tmp.w;
ww = 0;
}
w[tmp.x][tmp.y] = ww;
if (tmp.y + 1 <= m && s1[tmp.x][tmp.y] == '0')
q.push(node(ww + 1, tmp.x, tmp.y + 1));
if (tmp.y > 1 && s1[tmp.x][tmp.y - 1] == '0')
q.push(node(ww + 1, tmp.x, tmp.y - 1));
if (tmp.x + 1 <= n && s2[tmp.x][tmp.y] == '0')
q.push(node(ww + 1, tmp.x + 1, tmp.y));
if (tmp.x > 1 && s2[tmp.x - 1][tmp.y] == '0')
q.push(node(ww + 1, tmp.x - 1, tmp.y));
}
printf("%lld\n", res);
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 2395ms, 内存消耗: 30708K, 提交时间: 2020-03-28 21:38:00
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
const int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
int g[2050][2050],d[2050][2050],n,m,p,x,y;
char a[2050][2050],b[2050][2050];
bool value[2050][2050],vis[2050][2050];
long long ans=0;
priority_queue<pair<int,pair<int,int> > > q;
int check(int x,int y,int u,int v)
{
if(u<1||u>n||v<1||v>m) return 0;
if(u+1==x) return b[u][v]=='0';
if(x+1==u) return b[x][v]=='0';
if(v+1==y) return a[u][v]=='0';
if(y+1==v) return a[u][y]=='0';
return 0;
}
int main()
{
scanf("%d%d%d",&n,&m,&p);
if(p==1)
return 0*printf("0");
for(int i=1;i<=n;++i)
scanf("%s",a[i]+1);
for(int i=1;i<=n-1;++i)
scanf("%s",b[i]+1);
for(int i=1;i<=p;++i)
{
scanf("%d%d",&x,&y);
value[x][y]=1;
}
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
d[i][j]=100000;
vis[x][y]=1;
q.push(mp(0,mp(x,y)));
while(!q.empty())
{
pair<int,pair<int,int> >t=q.top();
q.pop();
pair<int,int> u=t.second;
int w=-t.first;
if(d[u.first][u.second]<=w) continue;
if(value[u.first][u.second])
{
ans+=w;
w=0;
}
d[u.first][u.second]=w;
for(int i=0;i<4;++i)
{
int x=u.first+dx[i],y=u.second+dy[i];
if(!check(u.first,u.second,x,y)) continue;
q.push(mp(-(w+1),mp(x,y)));
}
}
printf("%lld\n",ans);
return 0;
}