1445 变色DNA

有一只特别的狼，它在每个夜晚会进行变色，研究发现它可以变成N种颜色之一，将这些颜色标号为0,1,2...N-1。研究发现这只狼的基因中存在一个变色矩阵，记为colormap，如果colormap[i][j]='Y'则这只狼可以在某一个夜晚从颜色i变成颜色j（一晚不可以变色多次），如果colormap[i][j]=‘N’则不能在一个晚上从i变成j色。进一步研究发现，这只狼每次变色并不是随机变的，它有一定策略，在每个夜晚，如果它没法改变它的颜色，那么它就不变色，如果存在可改变的颜色，那它变为标号尽可能小的颜色（可以变色时它一定变色，哪怕变完后颜色标号比现在的大）。现在这只狼是颜色0，你想让其变为颜色N-1，你有一项技术可以改变狼的一些基因，具体说你可以花费1的代价，将狼的变色矩阵中的某一个colormap[i][j]='Y'改变成colormap[i][j]='N'。问至少花费多少总代价改变狼的基因，让狼按它的变色策略可以从颜色0经过若干天的变色变成颜色N-1。如果一定不能变成N-1，则输出-1.

Input

多组测试数据，第一行一个整数T，表示测试数据数量，1<=T<=5

每组测试数据有相同的结构构成：

每组数据第一行一个整数N,2<=N<=50。

之后有N行，每行N个字符，表示狼的变色矩阵，矩阵中只有‘Y’与‘N’两种字符，第i行第j列的字符就是colormap[i][j]。

Output

每组数据一行输出，即最小代价，无解时输出-1。

---

错误日志： \(gan\)他\(ma\)的字符串输入

解决方法： 老老实实一次读一行

---

Solution

现在被字符串搞得有点暴躁

（深呼吸， 呼）

这是一题解法很秒的图论题

首先把颜色抽象为点

因为变异优先选择编号较小的节点， 要是我们想让他选择编号靠后的点， 必须把前面所有的选择删去

所以有了一个大概思路： 对于从 \(u\) 开始的一种变异 \(v\) ， \(v\) 前面有 \(x\) 种颜色， 那么变异到 \(v\) 的代价为 \(x\)

抽象到图上， 有 \(if(map[u][v] == 'Y')u \rightarrow v (dis = x)\)

现在考虑连边真实意义：从 \(u\) 想变异为 \(v\) ， 需要删去前 \(x\) 种变异选项， 代价为 \(x\)

那么问题来了， 我们不能把改变以后的选择变回来， 那么会不会存在一种情况使得我们前面删错了选项， 错过了最优解呢？

又返回到图上， 一个点代表一个颜色， 假设删去的点还能重置， 那么满足上面条件的图上意义为：

从 \(u\) 点出发， 经过一个环后返回 \(u\) 点， 并且选择一条新边继续遍历

因为走的是最短路， 所以上述情况不存在

图上意义与其真实意义紧密结合， 是这题的妙处

Code

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

#define LL long long

using namespace std;

int RD(){

    int out = 0,flag = 1;char c = getchar();

    while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}

    while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}

    return flag * out;

    }

const int maxn = 1019,INF = 1e9 + 19;

int head[maxn],nume = 1;

struct Node{

    int v,dis,nxt;

    }E[maxn << 3];

void add(int u,int v,int dis){

    E[++nume].nxt = head[u];

    E[nume].v = v;

    E[nume].dis = dis;

    head[u] = nume;

    }

int T, len;

char s[maxn];

int d[maxn];

bool inq[maxn];

void SPFA(int s){

	queue<int>Q;

	d[s] = 0;

	Q.push(s);

	inq[s] = 1;

	while(!Q.empty()){

		int u = Q.front();Q.pop();inq[u] = 0;

		for(int i = head[u];i;i = E[i].nxt){

			int v = E[i].v, dis = E[i].dis;

			if(d[u] + dis < d[v]){

				d[v] = d[u] + dis;

				if(!inq[v])Q.push(v), inq[v] = 1;

				}

			}

		}

	}

void init(){

	for(int i = 1;i <= len;i++)d[i] = INF;

	memset(head, 0 ,sizeof(head));

	nume = 1;

	}

int main(){

	T = RD();

	while(T--){

		len = RD();

		init();

		for(int i = 1;i <= len;i++){

			scanf("%s", s);

			int cnt = 0;

			for(int j = 0;j < len;j++){

				if(s[j] == 'Y')add(i, j + 1, cnt++);

				}

			}

		SPFA(1);

		if(d[len] == INF)puts("-1");

		else printf("%d\n", d[len]);

		}

	return 0;

	}